#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=300010; int n,m,a[MAXN],b[MAXN],p[MAXN],v[MAXN]; int ans1,ans2; void solve(int *a,int *b,int w,int delta) { if(delta==1) { int insert=upper_bound(a+1,a+n+1,w)-a-1; a[insert]++; ans1+=b[n-insert+1]; ans2+=b[insert]; } else { int insert=lower_bound(a+1,a+n+1,w)-a; a[insert]--; ans1-=b[n-insert+1]; ans2-=b[insert]; } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; p[i]=a[i]; } for(int i=1;i<=n;i++) { cin>>b[i]; v[i]=b[i]; } sort(a+1,a+n+1); sort(b+1,b+n+1); for(int i=1;i<=n;i++) { ans1+=(ll)a[i]*b[n-i+1];//强制转换 ans2+=(ll)a[i]*b[i]; } cout<<ans1<<" "<<ans2<<endl; if(m==0) { return 0; } for(int i=1;i<=m;i++) { int ty,x,delta; cin>>ty>>x>>delta; if(ty==1) { solve(a,b,p[x],delta); p[x]+=delta; } else { solve(b,a,v[x],delta); v[x]+=delta; } cout<<ans1<<" "<<ans2<<endl; } return 0; }
//变量名不能用min和max！=_=
//数据类型不同时计算要加（数据类型（转换后））再计算
//upper_bound和lower_bound真的好用！+_+
//头文件<algorithm>
//第一个大于等于k的位置在：lower_bound(a,a+n,k)-a+1
//第一个大于k的位置在：upper_bound(a,a+n,k)-a+1
1.1 n, m ≤ 10 每次修改完后，枚举所有可能的 n! 种配对方案，计算最大、最小值。 时间复杂度 O(m ∗ n!)。期望得分：10.
1.2 n, m ≤ 2000 注意到最小的质量之和一定是将 p 和 v 分别按从小到大和从大到小排序，并将对应数字分别配对。 最大的质量之和是将 p 和 v 均按从小到大排序，将对应数字分别配对。 每次修改后在有序的数组中二分修改的数字，则只需要将该数字的位置进行调整，就能得到有序的 数组。每次修改完后 O(n) 统计答案。 1时间复杂度 O(nm)。期望得分：55.
1.3 正解 参照 1.2 的做法，注意到 |delta| = 1，若 delta = 1，则找到修改的数字在有序数组中最后一次出 现的位置，将该位置的数 +1，得到的仍然是一个有序的数组，只要修改这一位对答案的贡献即可。同 理当 delta = −1 时，找到修改的数在有序数组中第一次出现的位置，令该位置上的数 −1 并维护答案。 时间复杂度 O(n log n)。期望得分：100.