题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 3 \times 10^5$。

每组数据输入$n$，$k(1 \leq k \leq n \leq 3 \times 10^5)$，长为$k$的数组$a(1 \leq a[i] \leq n)$，长为$k$的数组$t(1 \leq t[i] \leq 10^9)$。

数轴上有$k$个正在制冷的空调，第$i$个空调的位置是$a[i]$，温度为$t[i]$。

位置$j$的温度会受到空调$i$的影响，离空调越远，温度越高，具体温度为$t[i]+|a[i]-j|$。

如果位置$j$被多个空调影响，取温度最小值。输出$1$~$n$每个位置的温度。

输入样例

5

6 2
2 5
14 16

10 1
7
30

5 5
3 1 4 2 5
3 1 4 2 5

7 1
1
1000000000

6 3
6 1 3
5 5 5

输出样例

15 14 15 16 16 17 
36 35 34 33 32 31 30 31 32 33 
1 2 3 4 5 
1000000000 1000000001 1000000002 1000000003 1000000004 1000000005 1000000006 
5 6 5 6 6 5 

算法

前后缀分解

将题目中的$a$数组和$t$数组封装到一个二元组数组$air$中，$air[i].pos=a[i]$，$air[i].t=t[i]$。

这个题的绝对值是比较讨厌的，但是我们可以比较容易地发现一种能够去掉绝对值的方法。对于某个位置$j$的空调，它左边$i$位置的空调对它温度的影响的距离部分$|j-i|=j-i$，右边$i$位置的空调对它温度的影响的距离部分$|j-i|=i-j$。

因此，我们可以维护两个有序多重集合（平衡树）。对于某个位置$j$，$left$存$j$左边空调的$air[i].t-air[i].pos$，$right$存$j$右边（包括$j$位置）空调的$air[i].t+air[i].pos$，此时我们可以$O(1)$获得$left$和$right$中的最小值，这个最小值加上$j$就是$j$位置的温度。我们不断遍历$j \in [1,n]$，动态维护$left$和$right$中的元素，就可以得到所有位置的温度。

复杂度分析

时间复杂度

先预处理出一个$t$数组，表示位置$i$的空调温度（多个空调的话就保留最低温度），预处理出这个数组需要对读入的空调位置和温度数组按照位置排序，时间复杂度为$O(klog_2k)$。

然后将所有空调的“位置加上温度”的值存入$right$中，由于是对平衡树的插入操作，时间复杂度为$O(klog_2k)$。

最后进行前后缀分解，遍历$j \in [1,n]$，动态维护$left$和$right$两棵平衡树时需要进行平衡树的插入和删除操作，时间复杂度是$O(log_2k)$的，因此这一步的时间复杂度为$O(nlog_2k)$。

综上，整个算法的时间复杂度为$O((n+k)log_2k)$。

空间复杂度

主要的空间消耗就是$t$数组和$left$、$right$两个平衡树。由于要存的位置是$[1,n]$，所以前者的空间复杂度为$O(n)$；后者两棵平衡树中需要放$k$个空调的信息，因此空间复杂度为$O(k)$。

综上，整个算法的额外空间复杂度为$O(n+k)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

const int N = 300010;
int T, n, k, t[N];
struct Air{
    int pos, t;
    bool operator<(const Air& other) const {
        return pos < other.pos;
    }
} air[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        multiset<int> left, right;
        for(int i = 1; i <= k; i++) {
            scanf("%d", &air[i].pos);
        }
        for(int i = 1; i <= k; i++) {
            scanf("%d", &air[i].t);
        }
        sort(air + 1, air + k + 1);
        // 每个位置只保留温度最低的空调温度
        for(int i = 1; i <= k; i++) {
            if(t[air[i].pos] == 0) {
                t[air[i].pos] = air[i].t;
            }else {
                t[air[i].pos] = min(t[air[i].pos], air[i].t);
            }
        }
        for(int i = 1; i <= n; i++) {
            if(t[i] > 0) right.insert(t[i] + i);
        }
        for(int j = 1; j <= n; j++) {
            if(left.size() && right.size()) {
                int l = *left.begin(), r = *right.begin();
                printf("%d ", min(l + j, r - j));
            }else if(left.size()) {
                int l = *left.begin();
                printf("%d ", l + j);
            }else if(right.size()) {
                int r = *right.begin();
                printf("%d ", r - j);
            }
            if(t[j] > 0) {
                right.erase(right.find(t[j] + j));
                left.insert(t[j] - j);
            }
        }
        puts("");
        for(int i = 1; i <= n; i++) {
            t[i] = 0;
        }
    }
    return 0;
}