原题链接

分析

• 前缀和和差分算法，能够用线性的时间解决问题，将时间复杂度降为O(n)
• 比如这道题，如果暴力的话，每次进行ai操作的时候都要进行循环，效率很低
• 一般题里只要说将某范围内测数据全部改变，就需要前缀和/差分算法

过程

1. 有一个b数组，称为差分数组，对v数组的操作结果都存在b数组里
2. 每次进行新一轮操作时，使用memset初始化，并且范围可以写一下优化
3. 然后对b数组进行前缀和处理
4. 进行判断输出，如果被操作过，那么前缀和项必有值，输出1 否则0

代码

#include "iostream"
#include "string.h"
using namespace std;
const int N=200010;
int b[N]={0};
int main(){
    int t=0,n=0;
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        memset(b, 0, 4 * (n + 1));
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            x=min(x,i);
            b[i - x + 1]++;
            b[i + 1]--;
        }
        for(int i=1;i<=n;i++){
            b[i]+=b[i - 1];
            if(b[i])printf("1 ");
                else printf("0 ");
        }
        printf("\n");
    }
}