题目描述
思路:
对于区间操作我们都尽量用差分来把他转化成点的操作
所以我们的思路就是
对于每次操作的范围【l,r】都用点标记
a[l] + 1 表示这段范围后都被这次操作标记
a[r + 1] - 1 表示r区间后不被这次操作标记
那么就只需要求前缀和就可以求出一段区间被操作几次
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
int a[N],c[N];
int T,n;
int main(){
cin >> T;
while(T--)
{
cin >> n;
for(int i = 1; i <= n; i++) scanf("%d",a + i);
memset(c,0,sizeof c);
for(int i = 1; i <= n; i++)
{
if(a[i] == 0) continue;
c[max(1,i - a[i] + 1)] ++ , c[i + 1] --;
}
for(int i = 1; i <= n; i++)
{
if(i != 1) putchar(' ');
c[i] += c[i-1];
printf("%d",c[i] ? 1 : 0);
}
putchar('\n');
}
return 0;
}