蓝桥杯每日一题汇总
动态维护一个区间,并且每次都要选一个区间加上 $1$,这很明显是一道差分题。
每次进行操作时,差分维护 $l - a[i] + 1$ 到 $l$,其中 $l$ 为当前区间的长度。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, a[N], b[N];
void insert(int l, int r, int c) {
b[l] += c, b[r + 1] -= c;
}
int main() {
int tt;
cin >> tt;
while (tt --) {
cin >> n;
memset(b, 0, sizeof b);
for (int i = 1; i <= n; i ++) {
cin >> a[i];
if (a[i] == 0) {
continue;
} else {
insert(max(1, i - a[i] + 1), i, 1);
}
}
for (int i = 1; i <= n; i ++)
b[i] += b[i - 1];
for (int i = 1; i <= n; i ++)
cout << (b[i] ? 1 : 0) << ' ';
cout << endl;
}
}