[ABC437D] Sum of Differences 题解

[ABC437D] Sum of Differences

思路

枚举A i A_iAi​，考虑有c n t 1 cnt1cnt1个B j ≤ A i B_j\le A_iBj​≤Ai​，这些B j B_jBj​的累加和为s 1 s1s1，有c n t 2 cnt2cnt2个B j > A i B_j> A_iBj​>Ai​，这些B j B_jBj​的累加和为s 2 s2s2。那么A i A_iAi​的贡献就是c n t 1 × A i − s 1 + s 2 − c n t 2 × A i cnt1\times A_i-s1+s2-cnt2\times A_icnt1×Ai​−s1+s2−cnt2×Ai​。

将A AA数组与B BB数组从小到大排序即可快速求出c n t 1 , c n t 2 , s 1 , s 2 cnt1,cnt2,s1,s2cnt1,cnt2,s1,s2。

代码

记得开 long long。

#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+5,mod=998244353;intn,m;longlonga[N],b[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<=m;i++)cin>>b[i];sort(a+1,a+1+n);sort(b+1,b+1+m);longlongs1=0,s2=0,cnt1=0,cnt2=m,ans=0;for(inti=1;i<=m;i++)s2=(s2+b[i])%mod;for(inti=1;i<=n;i++){while(cnt1<m&&b[cnt1+1]<=a[i])cnt1++,s1=(s1+b[cnt1])%mod,cnt2--,s2=(s2-b[cnt1])%mod;ans=(ans+a[i]*cnt1-s1+s2-a[i]*cnt2)%mod;}cout<<(ans+mod)%mod;return0;}