备战蓝桥杯Day4差分

差分(修改区间后查询) 1.要点 a[0]=0; for(int i=1;i<=n;i++){ diff[i]=a[i]-a[i-1];//构建差分数组 } //原数组a区间[l,r]全部加上x diff[l]+=x;//还原a数组[l,n]全部加上x diff[r+1]-=x;//还原a数组[r+1,n]全部减去x for(int i=1;i<=n;i++){ a[i]=a[i-1]+diff[i]; }

实现多次修改完后多次查询,不能实现边修改边查询

2.例题 2022重新排序

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

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+9; ll a[N],b[N],bdiff[N];//b[N]为位置查询次数数组.bdiff[N]为位置查询次数差分数组 int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int m; cin>>m; ll res=0,sumA=0,sumB=0; while(m--){ ll l,r; cin>>l>>r; bdiff[l]+=1; bdiff[r+1]-=1; } for(int i=1;i<=n;i++){ b[i]=b[i-1]+bdiff[i];//b[i]为每个位置查询次数 } for(int i=1;i<=n;i++){ sumA+=a[i]*b[i];//查询次数*数字=总和 } sort(a+1,a+1+n),sort(b+1,b+1+n);//两个数组均排序就能实现大数字在次数高位 for(int i=1;i<=n;i++){ sumB+=a[i]*b[i]; } res=sumB-sumA; cout<<res; return 0; } 2018三体攻击

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