思路:
1.操作1是每次先向队尾加入一个0.
2.如果a[i]!=0,那么我们要将最后a[i]个数变为1.
3.很明显这是区间修改操作,我们可以用差分。
差分O(1)进行区间修改:
1.如果我们想让数组a[l]到a[r]这个范围内的元素都加上一个数c。
2.可以构建差分数组b,b[i] = a[i] - a[i-1];
3.如果我们将b[l] += c,b[r+1] -=c,那么我们求b的前缀和数组,得到的就是l---r区间都加上c的a。
本题实现:
1.遍历1到n,
2.如果a[i]为0就继续。
3.如果a[i]不为0,我们对差分数组进行操作(本题差分数组初识为0,不用特意求)。
4.对要变为1的区间左端点l元素+1,右端点r+1处减一
5.最后对差分数组求一遍前缀和就是答案。
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
const int N = 2e5 + 10;
const int R = (1 << 20) + 10;
const int Base = N / 2;
const int M = 2 * N;
const int P = 1 << 10;
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
const double eps = 1e-4;
const int mod = 998244353;
int n, m, k;
rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
int a[N];
void solve()
{
scanf("%d", &n);
int cnt = 0;
vector<int> s(n + 2);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++)
{
cnt++;
if (a[i])
{
int l = max(1, cnt - a[i] + 1);
int r = cnt + 1;
s[l] += 1;
s[r] += -1;
}
}
for (int i = 1; i <= n; i++)
{
s[i] = s[i - 1] + s[i];
// cout << i << ' ' << s[i] << endl;
if (s[i] > 0)
{
printf("1 ");
}
else
{
printf("0 ");
}
}
cout << endl;
}
int main()
{
int t = 1;
// init(10010);
scanf("%d", &t);
while (t--)
{
// cout << -0x3f3f3f3f << endl;
solve();
}
}
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/