AcWing
3729. 改变数组元素
法一：类似区间维护的方法。假设数组V的长度为n, 元素与a相同，其中的元素则表示要向前更新的长度。维护一个更新阈lf，在数组V的[lf - j](j是从右到左迭代数组V的当前迭代)区间的元素需要更新为1。如果当前迭代的阈值更新使得lf更小，则更新lf.
#include <bits/stdc++.h>
using namespace std;
// 区间维护
vector<int> a;
int main(){
int t;
cin >> t;
for(int i = 0; i <= t - 1; i++){
int n;
cin >> n;
a.resize(n);
for(int j = 0; j <= n - 1; j++){
cin >> a[j];
}
int lf = n;
for(int j = n - 1; j >= 0; j--){
lf = min(lf, j - a[j] + 1);
if(lf <= j) a[j] = 1;
}
for(int j = 0; j <= n - 1; j++) cout << a[j] << " \n"[j == n - 1];
}
}
法二：维护差分数组。b[i] = a[i] - a[i - 1], b[0] = a[0].
区间修改，将区间首元素+c，区间尾元素之后的第一个元素-c.
求数组a中某个位置的值，a[i] = b[0] + b[1] + ... + b[i].
求数组a，for(int i = 1; i <= n - 1; i++) b[i] += b[i - 1]; 此后，b数组中元素的值即为a数组中元素的值。
int a[], x = !!a[i]表示：$x = 0, a = 0$；$x = 1, a \not ={0}$.
因为题目涉及到区间更新，使用差分数组维护每个元素被更新的次数，可以做到O(1)复杂度的更新，n次更新，总体的时间复杂度为O(n).
#include <bits/stdc++.h>
using namespace std;
// 差分数组，b[i] = a[i] - a[i - 1]
vector<int> b(2*10e5+10);
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
fill(b.begin(), b.begin() + n, 0);
for(int i = 0; i <= n - 1; i++){
int a;
cin >> a;
a = min(a, i + 1);
b[i - a + 1]++;
b[i + 1]--;
}
for(int i = 1; i <= n - 1; i++) b[i] += b[i - 1];
for(int i = 0; i <= n - 1; i++) cout << !!b[i] << " \n"[i == n - 1];
}
return 0;
}