作为我以后的模板吧
#include<cstdio> #include<cctype> #include<algorithm> using namespace std; const int maxn=150002; int n,m,rt,w[maxn],tr[maxn][2],mx[maxn],siz[maxn],rev[maxn],tag[maxn],fa[maxn]; inline void read(int &x){ char ch=getchar();x=0;int f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} x*=f; } inline void pushup(int x){ mx[x]=max(w[x],max(mx[tr[x][0]],mx[tr[x][1]])); siz[x]=1+siz[tr[x][0]]+siz[tr[x][1]]; } void pushdown(int x){ if(tag[x]){ if(tr[x][0]){tag[tr[x][0]]+=tag[x];mx[tr[x][0]]+=tag[x];w[tr[x][0]]+=tag[x];} if(tr[x][1]){tag[tr[x][1]]+=tag[x];mx[tr[x][1]]+=tag[x];w[tr[x][1]]+=tag[x];} tag[x]=0; } if(rev[x]){ rev[tr[x][0]]^=1;rev[tr[x][1]]^=1; swap(tr[x][0],tr[x][1]); rev[x]=0; } } void rotate(int x,int &wher){ int old=fa[x],oldf=fa[old],whic=(tr[old][1]==x); if(old==wher)wher=x;else tr[oldf][tr[oldf][1]==old]=x; fa[x]=oldf;fa[old]=x;fa[tr[x][whic^1]]=old; tr[old][whic]=tr[x][whic^1];tr[x][whic^1]=old; pushup(old);pushup(x); } void splay(int x,int &wher){ while(x!=wher){ int old=fa[x],oldf=fa[old]; if(old!=wher)rotate((tr[old][1]==x)==(tr[oldf][1]==old)?old:x,wher); rotate(x,wher); } } int find(int x,int rk){ if(tag[x]||rev[x])pushdown(x); if(siz[tr[x][0]]+1==rk)return x; else if(siz[tr[x][0]]>=rk)return find(tr[x][0],rk); else return find(tr[x][1],rk-siz[tr[x][0]]-1); } void updataad(int l,int r,int ad){ int ll=find(rt,l),rr=find(rt,r+2); splay(ll,rt);splay(rr,tr[ll][1]); int z=tr[rr][0]; tag[z]+=ad;mx[z]+=ad;w[z]+=ad; } inline int query(int l,int r){ int x=find(rt,l),y=find(rt,r+2); splay(x,rt);splay(y,tr[x][1]); return mx[tr[y][0]]; } inline void updatarev(int l,int r) { int x=find(rt,l),y=find(rt,r+2); splay(x,rt);splay(y,tr[x][1]); int z=tr[y][0]; rev[z]^=1; } inline void build(int l,int r,int fath){ if(l>r)return; if(l==r){siz[l]=1;tr[fath][l>fath]=l;mx[l]=w[l];fa[l]=fath;return;} int mid=l+r>>1; fa[mid]=fath;tr[fath][mid>fath]=mid; build(l,mid-1,mid);build(mid+1,r,mid); pushup(mid); } int main(){ mx[0]=-2e9; read(n);read(m); build(1,n+2,0);rt=(n+3)>>1; while(m--){ int opt,x,y,z;read(opt);read(x);read(y); switch(opt){ case 1:read(z);updataad(x,y,z);break; case 2:updatarev(x,y);break; case 3:printf("%d\n",query(x,y));break; } } return 0; }转载于:https://www.cnblogs.com/MikuKnight/p/9330331.html
