备战蓝桥杯 Day4 差分

差分(修改区间后查询)

1.要点

1. a[0]=0;
2. for(int i=1;i<=n;i++){
3.         diff[i]=a[i]-a[i-1];//构建差分数组
4. }
5. //原数组a区间[l,r]全部加上x
6. diff[l]+=x;//还原a数组[l,n]全部加上x
7. diff[r+1]-=x;//还原a数组[r+1,n]全部减去x
8. for(int i=1;i<=n;i++){
9.         a[i]=a[i-1]+diff[i];
10. }

复制代码

实现多次修改完后多次查询,不能实现边修改边查询
2.例题

2022重新排序

利用差分+1-1获得数组每个位置的查询次数(可简化为一个数组)，而查询次数*数字=总和，要排序只需原数组和查询次数数组均升序即可实现数字越大，查询次数越大，再利用查询次数*数字=总和，只不过第一次可以利用前缀和

1. #include <bits/stdc++.h>
3. using namespace std;
5. typedef long long ll;
6. const int N=1e5+9;
7. ll a[N],b[N],bdiff[N];//b[N]为位置查询次数数组.bdiff[N]为位置查询次数差分数组
9. int main(){
10.         ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
11.         int n;
12.         cin>>n;
13.         for(int i=1;i<=n;i++){
14.                 cin>>a[i];
15.         }
16.         int m;
17.         cin>>m;
18.         ll res=0,sumA=0,sumB=0;
19.         while(m--){
20.                 ll l,r;
21.                 cin>>l>>r;
22.                 bdiff[l]+=1;
23.                 bdiff[r+1]-=1;
24.         }
25.         for(int i=1;i<=n;i++){
26.                 b[i]=b[i-1]+bdiff[i];//b[i]为每个位置查询次数
27.         }
28.         for(int i=1;i<=n;i++){
29.                 sumA+=a[i]*b[i];//查询次数*数字=总和
30.         }
31.         sort(a+1,a+1+n),sort(b+1,b+1+n);//两个数组均排序就能实现大数字在次数高位
32.         for(int i=1;i<=n;i++){
33.                 sumB+=a[i]*b[i];
34.         }
35.         res=sumB-sumA;
36.         cout<<res;
37.         return 0;
38. }

复制代码

2018三体攻击

三维差分太困难，现在先不纠结，之后遇到太难的题目不要浪费时间，暴力拿分跳过，此题学习到:
1.三维数组不能开太大，否则编译不通过，可以第一维开3000，后两维开200
2.多层for中直接退出先输出答案然后exit(0)，不消break

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。