做响应式网站用什么框架,大连弗莱科技官方网站,千峰网课,wordpress 4 xmlrpc本题链接#xff1a;登录—专业IT笔试面试备考平台_牛客网
题目#xff1a;
样例#xff1a; 输入 3 2
1 2 3
1 2 4
3 3 -2 输出 5 6 1 思路#xff1a; 一直以来#xff0c;我总是不太理解差分和树状数组操作区别。 现在摸了一下开始有所理解了。 差分和树状数组的区别…本题链接登录—专业IT笔试面试备考平台_牛客网
题目
样例
输入 3 2
1 2 3
1 2 4
3 3 -2
输出 5 6 1 思路 一直以来我总是不太理解差分和树状数组操作区别。 现在摸了一下开始有所理解了。 差分和树状数组的区别 树状数组可以边区间插入操作边查询。 差分一系列区间操作后最后确定结果序列 差分原理
设 原数组为 a 差分数组为 b 前缀和数组为 c
这里要注意的是操作差分的时候x 前后的关系 差分 就是 差分数组的前缀和 原数组相应位置的前缀和 例如 b1 a1 - 0 b2 a2 - a1 b3 a3 - a2
b1 b2 b3 c3c3 a1 a2 a3
所以相应关系后操作差分数组函数如下理解相应核心内容
初始时添加数值序列
for(int i 1,x;i n;i)
{cin x;Insert(i,i,x);
}
区间添加修改函数
inline void Insert(int l, int r, int x)
{a[l] x; // 前缀和 a[l] x;a[r 1] - x; // 区间 a[r] 因为前面 x 了所以要维持差分前缀和不变所以 r1 - x
}
获取最终操作结果序列函数
inline void getArray()
{for (int i 1; i n; i) // 最后求 差分的前缀和{a[i] a[i - 1]; // 差分的前缀和就是相应原数组操作后的前缀和}
}
代码详解如下
#include iostream
#include vector
#include queue
#include cstring
#include algorithm
#include unordered_map
#define endl \n
#define int long long
#define YES puts(YES)
#define NO puts(NO)
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,Ofast,inline)
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N 2e6 10;
inline void solve();signed main()
{
// freopen(a.txt, r, stdin);IOS;int _t 1;
// cin _t;while (_t--){solve();}return 0;
}
int n,q,a[N];inline void Insert(int l,int r,int x)
{a[l] x;a[r 1] - x;
}
inline void getArray()
{for(int i 1;i n;i){a[i] a[i - 1];}
}
inline void solve()
{cin n q;for(int i 1,x;i n;i){cin x;Insert(i,i,x); // 初始插入序列}while(q--){int l,r,x;cin l r x;Insert(l,r,x); // 区间修改}getArray(); // 获取最后系列操作后结果序列for(int i 1;i n;i) cout a[i] ;
}
最后提交
