首页 > 代码库 > 【BZOJ3745】[Coci2015]Norma cdq分治
【BZOJ3745】[Coci2015]Norma cdq分治
【BZOJ3745】[Coci2015]Norma
Description
Input
Output
Sample Input
2
4
1
4
Sample Output
【数据范围】
N <= 500000
1 <= a_i <= 10^8
题解：最近做这种题好像有点多啊~（虽然我基本上都没A）。
比较直接的想法就是找出区间的最大值mid，然后分治处理[l,mid-1]和[mid+1,r]，但是这就要求我们在统计[l,r]的答案时，花费的时间不超过较短的那个区间的长度，于是比较难搞，所以我们还是考虑cdq分治。
我们从右往左枚举[l,mid]中的每个点i，设[i,mid]中的最小值为mn，最大值为mx。同时在[mid+1,r]中维护两个指针a,b，满足min[mid+1,a]>=mn，max[mid+1,b]<=mx。假设a<b，那么[mid+1,r]就被我们分成了三块，我们分别考虑j在每个块内的答案。
1.j<=a：$ans+=mx\times mn\sum\limits_{j=mid+1}^a(j-i+1)$等差数列算一下即可
2.a<j<=b：$ans+=mx\times \sum\limits_{j=a+1}^bmin[a+1,j]\times(j-i+1)\\=mx\times(\sum\limits_{j=a+1}^bmin[a+1,j]*j-\sum\limits_{j=a+1}^bmid[a+1,j]*(i-1))$，我们预处理出$\sum\limits_{j=a+1}^bmin[a+1,j]*j$和$\sum\limits_{j=a+1}^bmid[a+1,j]$即可。
3.b<j<=r：$ans+=\sum\limits_{j=b+1}^rmin[b+1,j]\times max[b+1,j] \times (j-i+1)=\sum\limits_{j=b+1}^rmin[b+1,j]\times max[b+1,j]\times j-\sum\limits_{j=b+1}^rmin[b+1,j]\times max[b+1,j]\times(i-1)$，我们预处理出$\sum\limits_{j=b+1}^rmin[b+1,j]\times max[b+1,j]\times j$和$\sum\limits_{j=b+1}^rmin[b+1,j]\times max[b+1,j]$即可。
写完题解发现上面那一坨latex是什么玩意~太丑了将就看吧~
#include <cstdio>#include <iostream>#include <cstring>using namespace std;typedef long long ll;const int maxn=500010;const ll mod=1000000000;const ll inf=1ll<<30;int n;ll ans;ll v[maxn],sn[maxn],cn[maxn],sm[maxn],cm[maxn],sw[maxn],cw[maxn];int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) {if(gc==‘-‘)f=-f; gc=getchar();} while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret*f;}void solve(int l,int r){ if(l==r) { ans=(ans+v[l]*v[l])%mod; return ; } int mid=l+r>>1,i,j,k; ll a,b; ll mx=0,mn=inf; solve(l,mid),solve(mid+1,r); for(sm[mid]=sn[mid]=sw[mid]=cm[mid]=cn[mid]=cw[mid]=0,i=mid+1;i<=r;i++) { mx=max(mx,v[i]),mn=min(mn,v[i]); sm[i]=(sm[i-1]+mx)%mod,sn[i]=(sn[i-1]+mn)%mod,sw[i]=(sw[i-1]+mx*mn)%mod; cm[i]=(cm[i-1]+mx*i)%mod,cn[i]=(cn[i-1]+mn*i)%mod; cw[i]=(cw[i-1]+mx*mn%mod*i)%mod; } for(i=j=k=mid,mx=0,mn=inf;i>=l;i--) { mx=max(mx,v[i]),mn=min(mn,v[i]); for(;j<r&&v[j]>=mn&&v[j+1]>=mn;j++); for(;k<r&&v[k]<=mx&&v[k+1]<=mx;k++); a=min(j,k),b=max(j,k); ans=ans+mx*mn%mod*((mid+a-i-i+3)*(a-mid)/2%mod)%mod; ans=((ans+cw[r]-cw[b]-(i-1)*(sw[r]-sw[b]))%mod+mod)%mod; if(j<k) ans=(ans+mx*(cn[b]-cn[a]-(i-1)*(sn[b]-sn[a])%mod)%mod+mod)%mod; else ans=(ans+mn*(cm[b]-cm[a]-(i-1)*(sm[b]-sm[a])%mod)%mod+mod)%mod; }}int main(){ n=rd(); int i; for(i=1;i<=n;i++) v[i]=rd(); solve(1,n); printf("%lld",ans); return 0;}//3 1 2 1【BZOJ3745】[Coci2015]Norma cdq分治