waitwolf 2019-12-19
然而好像没有平衡树
还是题解包:
树上主席树+启发式合并。
然而好像知道标签就没啥了。在启发式合并时可以顺手求lca
然而这题好像可以时间换空间(回收空间)
难点在于考虑贡献的来源
考虑一个区间两端点和区间最值(不含端点)的关系
小,中,大:贡献p1
大,小,大:贡献p2
大,中,小:贡献p1
则预处理出每个点左右第一个比它大的数的位置,设为l和r
则l会对r有p2的贡献,l会对i+1~r-1产生p1的贡献,同理r会对l+1~i-1产生p1的贡献。
用线段树维护扫描线,正向,逆向分别扫一遍,先把贡献都加进线段树,扫到某个点时先统计贡献再在线段树中减掉贡献。
具体实现见代码
#include<bits/stdc++.h> #define LL long long #define N 200050 using namespace std; struct node{int l,r,id;LL ans;}q[N]; const int inf=1000000007; int n,m,p1,p2; int a[N]; int l[N],r[N],dq[N],ba; vector<pair<int,int> >v[N]; #define pb push_back #define mmp make_pair #define F first #define S second inline bool cmp1(const node &a,const node &b){return a.l<b.l;} inline bool cmp2(const node &a,const node &b){return a.r>b.r;} inline bool cmp(const node &a,const node &b){return a.id<b.id;} struct Segment_tree{ LL sum[N<<2],tag[N<<2]; inline void clear(){ memset(sum,0,sizeof(sum)); memset(tag,0,sizeof(tag)); } inline void upd(int g){sum[g]=sum[g<<1]+sum[g<<1|1];} inline void down(int g,int l,int m,int r) { tag[g<<1]+=tag[g]; tag[g<<1|1]+=tag[g]; sum[g<<1]+=tag[g]*(m-l+1); sum[g<<1|1]+=tag[g]*(r-m); tag[g]=0;return; } inline void add(int g,int l,int r,int x,int y,int v){ if(l>y||r<x)return; if(l>=x&&r<=y){sum[g]+=v*(r-l+1);tag[g]+=v;return;} const int m=l+r>>1; if(tag[g])down(g,l,m,r); add(g<<1,l,m,x,y,v); add(g<<1|1,m+1,r,x,y,v); upd(g); } inline LL ask(int g,int l,int r,int x,int y) { if(l>y||r<x)return 0; if(l>=x&&r<=y)return sum[g]; const int m=l+r>>1; if(tag[g])down(g,l,m,r); return ask(g<<1,l,m,x,y)+ask(g<<1|1,m+1,r,x,y); } }T; int main() { // freopen("da.in","r",stdin); scanf("%d%d%d%d",&n,&m,&p1,&p2); for(int i=1;i<=n;++i)scanf("%d",&a[i]); for(int i=1;i<=m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i; a[0]=inf;a[n+1]=inf-1; for(int i=1;i<=n+1;++i){ while(a[i]>a[dq[ba]]){ r[dq[ba]]=i; v[l[dq[ba]]].pb(mmp(dq[ba]+1,i-1)); --ba; } l[i]=dq[ba];dq[++ba]=i; } // for(int i=1;i<=n;++i) // printf("l[%d]=%d r[%d]=%d\n",i,l[i],i,r[i]); sort(q+1,q+m+1,cmp1); for(int i=1;i<=n;++i){ if(r[i]!=i+1)T.add(1,1,n,r[i],r[i],p1); for(int j=v[i].size()-1;~j;--j) T.add(1,1,n,v[i][j].F,v[i][j].S,p2); } for(int i=1,k=1;i<=n;++i){ while(q[k].l==i&&k<=m){ q[k].ans+=T.ask(1,1,n,i,q[k].r); ++k; } if(r[i]!=i+1)T.add(1,1,n,r[i],r[i],-p1); for(int j=v[i].size()-1;~j;--j) T.add(1,1,n,v[i][j].F,v[i][j].S,-p2); v[i].clear(); } for(int i=1;i<=n;++i) if(r[i])v[r[i]].push_back(mmp(l[i]+1,i-1)); sort(q+1,q+m+1,cmp2); for(int i=n;i;--i){ if(l[i]!=i-1)T.add(1,1,n,l[i],l[i],p1); for(int j=v[i].size()-1;~j;--j) T.add(1,1,n,v[i][j].F,v[i][j].S,p2); } for(int i=n,k=1;i;--i){ while(q[k].r==i&&k<=m){ q[k].ans+=T.ask(1,1,n,q[k].l,i); ++k; } if(l[i]!=i-1)T.add(1,1,n,l[i],l[i],-p1); for(int j=v[i].size()-1;~j;--j) T.add(1,1,n,v[i][j].F,v[i][j].S,-p2); } // printf("%d %d %lld\n",q[2].l,q[2].r,q[2].ans); sort(q+1,q+m+1,cmp); for(int i=1;i<=m;++i) printf("%lld\n",q[i].ans+1ll*(q[i].r-q[i].l)*p1); return 0; }