3729. 改变数组元素(差分)

https://www.acwing.com/problem/content/3732/

一维差分,要点是题目给的v数组一开始为空的,可以认为v数组一开始全为0,有n个0(因为加入了n个数),要满足题意得用循环模拟不断往v数组中加入数
在加入数的途中不断的构造差分数组,每次加入一个数都去判断是否满足有ai个数,不满足就设ai为i,这样就满足了题意,即便ai为0,也不会改变差分数组
即便ai大于i,也只是将目前所有位改为1

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 2e5+10;
int n,b[N];
int t;

int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n;
        memset(b,0,(n+1)*4);//只清除更改的区间,而不是全部,时间复杂度低
        for(int i=1;i<=n;i++)//不断地为v数组加入数
        {
            int x;
            cin >> x;
            if(x>i)x=i;
            int l=i-x+1,r=i;//计算区间
            b[l]+=1;//构造差分
            b[r+1]-=1;
        }
        for(int i=1;i<=n;i++)
        {
            b[i]=b[i-1]+b[i];//构造差分前缀和数组,也就是v数组
        }
        for(int i=1;i<=n;i++)
            cout << !!b[i] << ' ';//!!在c++中只会返回0或1,若b[i]为0,则反一次为1,再反一次为0
            //若b[i]>=1,比如233,那么233反一次为0,再反一次为1
        cout << endl;
    }
}