差分数组的基础应用
写篇博客来帮自己理解下
本题一下就想出思路了(写不对) 常态
开始正 题
向下看
本题的标签为差分数组 好吧 bu用差分好像更短
首先本题就只有两种操作
1 插入
2 修改
woc 这不线段树吗?(dalao 轻喷)
嗝屁,开个玩笑拉
要全加1 首先肯定想到可以差分 需要用多少个数组去维护
大家应该经常看到b[i] += b[i - 1]这种操作 (YG只对空数组用) b[i] = b[i] + b[i - 1];
本蒟蒻却经常不理解
今天 发现 这其实也差不多就是一个标记的问题 还有前缀和逆推的问题
因为假设a[i] 为b[i]所对应的数组 那么就会有 a[i] = b[i]的前缀和(https://https://oi-wiki.org/basic/prefix-sum/#%E5%B7%AE%E5%88%86)
而这里的 b[i] += b[i - 1] 处理之后的b[i]就表示前i个b[i]的和也就是修改后的数组的美意项
的值 所以直接处理就可以了(因为刚是个空数组 !!!进行差分操作前要注意初始化)
总算是搞明白了
#include<bits/stdc++.h>
using namespace std;
#define debug printf(" ++ zhangyx ++ ");
#define int long long
typedef pair<int,int> PII;
const int N = 1e6;
const int INF = 0x7f7f7f7f;
int n,a[N + 5];
void solve() {
int cnt = 0;
int v[N + 5],b[N + 5];
cin >> n;
for (int i = 1;i <= n;i ++) cin >> a[i];
for (int i = 1;i <= n + 1;i ++) b[i] = 0;
for (int i = 1;i <= n;i ++) {
if (a[i] != 0) {
int l = max((int)1,i - a[i] + 1),r = i;
b[l] += 1;
b[r + 1] -= 1;
}
}
//for (int i = 1;i <= cnt;i ++) b[i] += b[i - 1];
//for (int i = 1;i <= cnt;i ++) v[i] += b[i];
for (int i = 1;i <= n;i ++) b[i] += b[i - 1];
for (int i = 1;i <= n;i ++) {
if (b[i] > 0) cout << 1 << " ";
else cout << 0 << " ";
}
cout << endl;
}
signed main() {
int T;cin >> T;
while (T --) solve();
}
喜欢就点个赞吧