AcWing
3729. 改变数组元素
法一:类似区间维护的方法。假设数组V
的长度为n
, 元素与a
相同,其中的元素则表示要向前更新的长度。维护一个更新阈lf
,在数组V
的[lf - j]
(j是从右到左迭代数组V的当前迭代)区间的元素需要更新为1。如果当前迭代的阈值更新使得lf
更小,则更新lf
.
#include <bits/stdc++.h>
using namespace std;
// 区间维护
vector<int> a;
int main(){
int t;
cin >> t;
for(int i = 0; i <= t - 1; i++){
int n;
cin >> n;
a.resize(n);
for(int j = 0; j <= n - 1; j++){
cin >> a[j];
}
int lf = n;
for(int j = n - 1; j >= 0; j--){
lf = min(lf, j - a[j] + 1);
if(lf <= j) a[j] = 1;
}
for(int j = 0; j <= n - 1; j++) cout << a[j] << " \n"[j == n - 1];
}
}
法二:维护差分数组。b[i] = a[i] - a[i - 1]
, b[0] = a[0]
.
区间修改,将区间首元素+c
,区间尾元素之后的第一个元素-c
.
求数组a
中某个位置的值,a[i] = b[0] + b[1] + ... + b[i]
.
求数组a
,for(int i = 1; i <= n - 1; i++) b[i] += b[i - 1]
; 此后,b
数组中元素的值即为a
数组中元素的值。
int a[]
, x = !!a[i]
表示:$x = 0, a = 0$;$x = 1, a \not ={0}$.
因为题目涉及到区间更新,使用差分数组维护每个元素被更新的次数,可以做到O(1)
复杂度的更新,n
次更新,总体的时间复杂度为O(n)
.
#include <bits/stdc++.h>
using namespace std;
// 差分数组,b[i] = a[i] - a[i - 1]
vector<int> b(2*10e5+10);
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
fill(b.begin(), b.begin() + n, 0);
for(int i = 0; i <= n - 1; i++){
int a;
cin >> a;
a = min(a, i + 1);
b[i - a + 1]++;
b[i + 1]--;
}
for(int i = 1; i <= n - 1; i++) b[i] += b[i - 1];
for(int i = 0; i <= n - 1; i++) cout << !!b[i] << " \n"[i == n - 1];
}
return 0;
}