【差分】改变数组元素

题目

3729. 改变数组元素 - AcWing题库

---

给定一个空数组 $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$ 个整数 $a_1,a_2,…,a_n$ 。

输出格式

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

数据范围

$1 \le T \le 20000$ ,
$1 \le n \le 2 \times 10^5$ ,
$0 \le a_i \le n$ ,
保证一个测试点内所有 $n$ 的和不超过 $2 \times 10^5$ 。

输入样例：

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$ 时输出 $0$ 其它情况输出均 $1$ 。

注意：$a_i$ 大于目前数组 $V$ 所包含的元素个数，不要越界了，此时视为将数组内所有元素变为 $1$ 。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = (int) 2e5 + 10;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int t = (int) in.nval;
        while (t-- > 0) {
            in.nextToken();
            int n = (int) in.nval;
            int[][] segs = new int[n][2];
            int[] b = new int[n + 1];
            for (int i = 0; i < n; ++i) {
                in.nextToken();
                int x = (int) in.nval;
                if (x != 0) {
                    ++b[Math.max(0, i - x + 1)];
                    --b[i + 1];
                }
            }
            int curr = 0;
            // Java输出太慢了 所以先把答案拼接起来再一起输出
            StringBuilder ans = new StringBuilder();
            for (int i = 0; i < n; ++i) ans.append((curr += b[i]) == 0 ? "0 " : "1 ");
            System.out.println(ans);
        }
    }
}