题目

给定一个空数组 $V$ 和一个整数数组 $a_1,a_2,…,a_n$。

现在要对数组 $V$ 进行 $n$ 次操作。

第 $i$ 次操作的具体流程如下：

  1. 从数组 $V$ 尾部插入整数 0。
  2. 将位于数组 $V$ 末尾的 $a_i$ 个元素都变为 1（已经是 1 的不予理会）。

注意：

  • $a_i$ 可能为 0，即不做任何改变。
  • $a_i$ 可能大于目前数组 $V$ 所包含的元素个数，此时视为将数组内所有元素变为 1。

请你输出所有操作完成后的数组 $V$。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

每组数据输出一行结果，表示所有操作完成后的数组 V，数组内元素之间用空格隔开。

数据范围

1≤T≤20000,
1≤n≤2×105,
0≤$a_i$≤n,
保证一个测试点内所有 n 的和不超过 2×105。

输入样例：

3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0

输出样例：

1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0

解题思路

区间合并

这道题本来标签是 差分 的，但是观察样例，结合题目思考，可以发现，数据只会变成1，不会变成0。也就是说一个数如果成了1之后就一直是1了。

那怎么判断会不会成1？

从题目理解：第i次操作，会改变(i-a[i],i]范围内的数字为1。注意左开右闭区间。那么写代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>

using namespace std;

int T, n, a[i];

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) {
            if (a[i]) {
                int j = max(0, i - a[i] + 1);
                for (j; j <= i; ++j) {
                    a[i] = 1;
                }
            }
        }
        for (int i = 0; i < n; ++i) cout << a[i] << " ";
        cout << endl;
    }
}

这个是最直观的，但是时间复杂度比较高，因为每次遍历到了一个非0的a[i]就要去遍历一次(i-a[i],i]。如果想要不再去遍历一次，就需要在外层循环遍历到i时就知道是否需要将a[i]改为1。然后发现它每一个a[i]都是决定包括自己在内的前面a[i]个数据是否变成1。所以有了思路：干脆从后往前遍历，记录一个左边界，左边界表示当前应该变成1的最左边的范围，其实就是i-a[i]。写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>

using namespace std;

int T, n, a[i];

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        int l = n;
        for (int i = n-1; i >= 0; --i) {
            l = min(l, i - a[i]);
            if (l < i) a[i] = 1;
        }
        for (int i = 0; i < n; ++i) cout << a[i] << " ";
        cout << endl;
    }
}

有了这个思路，可以改变一下题目

将位于数组 $V$ 末尾的 $a_i$ 个元素都变为 1（已经是 1 的不予理会）。 ==>

将位于数组 $V$ 末尾的 $a_i$ 个元素都变为 1（已经是 1 的改成 0 ）。

思考一下代码。思考完之后再点开结果。

点击查看结果

if (l < i) a[i] = 1;
改成：
if (l < i) a[i] ^= a[i];

时间复杂度：$O(n)$

差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2*1e5+5;
int T, n, a[N], d[N];

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        memset(d, 0, n*sizeof(int));
        
        for (int i = 0; i < n; ++i) {
            if (a[i]) {
                if (i-a[i]+1 < 0) a[i] = i+1;
                ++d[i-a[i]+1];
                --d[i+1];
            }
        }

        for (int i = 0; i < n; ++i) if (i) d[i] += d[i-1];
        
        for (int i = 0; i < n; ++i) {
            if (d[i]) cout << "1 ";
            else cout << "0 ";
        }

        cout << endl;
    }

    return 0;
}

这道题的差分的思想和常规的不一样。常规的可能是要记录操作的次数吗，然后直接输出这个值。但是这里实际上是根据被操作的次数，来判断是0还是1.如果被操作的次数不为0，则输出1，为0输出0。

时间复杂度是$O(n)$和上一种一样（但多了一次计算前缀和的遍历，所以其实时间应该也是比不过的）。但是空间复杂度明显要多一个差分数组d。所以没有上一种方法好。

同样，改变一下题目：

用差分怎么解决。

提示：考虑操作次数。

将位于数组 $V$ 末尾的 $a_i$ 个元素都变为 1（已经是 1 的不予理会）。 ==>

将位于数组 $V$ 末尾的 $a_i$ 个元素都变为 1（已经是 1 的改成 0 ）。

答案：

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < n; ++i) {
    if (d[i]) cout << "1 ";
    else cout << "0 ";
}

==>
    
for (int i = 0; i < n; ++i) {
    if (d[i] & 1) cout << "1 ";
    else cout << "0 ";
}