本文最后更新于 719 天前,其中的信息可能已经有所发展或是发生改变。
Original link
思想:
- 前缀和与差分。
- 对于
a[i]
的操作,构建差分数组 b[i]
记录被操作的区间。
- 利用前缀和可知所有被操作的区间,即
b[i] != 0
的区间。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 1e6 + 3; |
| |
| int a[N], b[N]; |
| |
| void solve(){ |
| int n; cin >> n; |
| for(int i = 1; i <= n; i ++){ |
| b[i] = 0; |
| cin >> a[i]; |
| } |
| for(int i = 1; i <= n; i ++){ |
| if(a[i] >= i) b[1] ++, b[i + 1] --; |
| else if(a[i] < i && a[i] != 0) b[i - a[i] + 1] ++, b[i + 1] --; |
| } |
| for(int i = 1; i <= n; i ++){ |
| b[i] += b[i - 1]; |
| if(b[i] != 0) cout << 1 << ' '; |
| else cout << 0 << ' '; |
| } |
| cout << endl; |
| } |
| |
| int main(){ |
| int _; cin >> _; |
| while(_ --) solve(); |
| return 0; |
| } |