posted on 2021-03-16 17:42:06 | under 题解 | source
题目可以转化一下：给一个长为 \(n\) 的数组 \(a\)，请求出一个长为 \(n\) 的数组 \(b\)。要求若 \(a_i\) 不为 \(0\)，则 \([b_{i-a_i+1},b_i]\) 这个区间要为 \(1\)。
知道这个题目意思就好办了。题目说 \(n\leq 2\times 10^5\)，暴力修改显然超时。我们可以用差分维护一下，每次给区间 \([b_{i-a_i+1},b_i]\) 加 \(1\)，最后没被加到的就是 \(0\)，反之是 \(1\)。这样 \(O(1)\) 区间加，\(O(n)\) 递推求原数组，不会超时。如果不会差分可以看这里。
//封装一个模版，用起来更方便
class Difference{//difference差分
private:
int a[100010],n;
public:
void clear(int size){//由于是多测，要清空
memset(a,0,sizeof a);
n=size;
}
void add(int l,int r,int c=1){//区间加
a[l]+=c,a[r+1]-=c;
}
void init(){//递推求原数组
for(int i=1;i<=n;i++){
a[i]+=a[i-1];
}
}
int operator[](int x)const{//访问
return a[x];
}
};
int n;
Difference a;
int mian(){
scanf("%d",&n);
a.clear(n);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
if(x) a.add(max(1,i-x+1),i);
}
a.init();
for(int i=1;i<=n;i++){
printf("%d ",min(1,a[i]));
//min(1,0)=0，min(1,非0数)=1，保证输出只有0和1
}
return puts(""),0;
}