差分
题干简析:每一个 ai 及 ai 前 ai 个数修改为 1,可以用差分的思想 将要修改为1的区域用 v[l] += 1 v[r + 1] -= 1 最后在前缀和一遍就可以了
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5 + 10;
int t, n;
int a[N] = {0}, v[N] = {0};
void insert(int l, int r){
v[l] += 1;
v[r + 1] -= 1;
}
int main(){
cin >> t;
while(t--){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
if(a[i]){
if(i - a[i] + 1 < 1) insert(1, i);
else insert(i - a[i] + 1, i);
}
}
for(int i = 1; i <= n; i++){
v[i] += v[i - 1];
cout << (v[i] > 0 ? 1 : 0) << ' ';
}
cout << endl;
memset(v, 0, sizeof v);
}
return 0;
}