备战蓝桥杯 Day4 差分
差分(修改区间后查询)1.要点
a=0;
for(int i=1;i<=n;i++){
diff=a-a;//构建差分数组
}
//原数组a区间全部加上x
diff+=x;//还原a数组全部加上x
diff-=x;//还原a数组全部减去x
for(int i=1;i<=n;i++){
a=a+diff;
}
实现多次修改完后多次查询,不能实现边修改边查询
2.例题
2022重新排序
利用差分+1-1获得数组每个位置的查询次数(可简化为一个数组)，而查询次数*数字=总和，要排序只需原数组和查询次数数组均升序即可实现数字越大，查询次数越大，再利用查询次数*数字=总和，只不过第一次可以利用前缀和
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+9;
ll a,b,bdiff;//b为位置查询次数数组.bdiff为位置查询次数差分数组
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;
}
int m;
cin>>m;
ll res=0,sumA=0,sumB=0;
while(m--){
ll l,r;
cin>>l>>r;
bdiff+=1;
bdiff-=1;
}
for(int i=1;i<=n;i++){
b=b+bdiff;//b为每个位置查询次数
}
for(int i=1;i<=n;i++){
sumA+=a*b;//查询次数*数字=总和
}
sort(a+1,a+1+n),sort(b+1,b+1+n);//两个数组均排序就能实现大数字在次数高位
for(int i=1;i<=n;i++){
sumB+=a*b;
}
res=sumB-sumA;
cout<<res;
return 0;
}
2018三体攻击
三维差分太困难，现在先不纠结，之后遇到太难的题目不要浪费时间，暴力拿分跳过，此题学习到:
1.三维数组不能开太大，否则编译不通过，可以第一维开3000，后两维开200
2.多层for中直接退出先输出答案然后exit(0)，不消break
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]