分析
首先注意到最后的答案形式上是一个长度为$n$的只包含0/1的序列,且是否为1只和这一段是否被变化过有关,与变化次数无关。将其记作$c$,对于第$i$次操作,其对c[l, r]产生影响。当第i次操作的第二步进行时,序列已经有i个数字。若$a_i!=0$,那么至少对于一个数字产生影响,右端点为i,由于$r-l+1=a_i$,左端点可计算为$max(1, i + 1 - a_i).$ 可以用差分数组$b$表示为$b[r + 1]-=1, b[l]+=1$ ,同时可以看出对于$a_i=0$仍正确。最后输出判断是否被加过即可,时间复杂度$O(n)$.
代码
#include<iostream>
#include<vector>
using namespace std;
const int N = 2e5 + 10;
int n;
void solve()
{
cin >> n;
vector<int> b(n + 2);
for(int i = 1; i <= n; ++i)
{
int x;
cin >> x;
b[i + 1] --;
b[max(1, i + 1 - x)] ++;
}
for(int i = 1; i <= n; ++i)
{
b[i] += b[i - 1];
cout << (bool)b[i] << " ";
}
cout << endl;
}
int main()
{
int T;
cin >> T;
while(T--) solve();
return 0;
}