裸的splay模板题。
支持修改，最值，翻转操作。
注意pushdown中写法。
By：大奕哥
1 #include2 using namespace std; 3 const int N=5e4+10; 4 int fa[N],c[N][2],lz[N],rev[N],mx[N],w[N],size[N],n,m,rt; 5 void pushdown(int x) 6 { 7 int l=c[x][0],r=c[x][1]; 8 if(lz[x]) 9 { 10 if(l)lz[c[x][0]]+=lz[x]; 11 if(r)lz[c[x][1]]+=lz[x]; 12 if(l)mx[c[x][0]]+=lz[x]; 13 if(r)mx[c[x][1]]+=lz[x]; 14 if(l)w[c[x][0]]+=lz[x]; 15 if(r)w[c[x][1]]+=lz[x]; 16 lz[x]=0; 17 } 18 if(rev[x]) 19 { 20 rev[x]^=1;rev[c[x][0]]^=1;rev[c[x][1]]^=1; 21 swap(c[x][0],c[x][1]); 22 } 23 size[x]=size[c[x][0]]+size[c[x][1]]+1; 24 mx[x]=max(w[x],max(mx[c[x][0]],mx[c[x][1]])); 25 } 26 void rotate(int x,int &k) 27 { 28 int y=fa[x],z=fa[y]; 29 int l=(c[y][1]==x);int r=l^1; 30 if(y==k)k=x;else c[z][c[z][1]==y]=x; 31 fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 32 c[y][l]=c[x][r];c[x][r]=y; 33 pushdown(y);pushdown(x); 34 } 35 void splay(int x,int &k) 36 { 37 while(x!=k) 38 { 39 int y=fa[x],z=fa[y]; 40 if(y!=k) 41 { 42 if(x==c[y][0]^y==c[z][0])rotate(x,k); 43 else rotate(y,k); 44 } 45 rotate(x,k); 46 } 47 } 48 int find(int x,int k) 49 { 50 if(!x)return 0;pushdown(x); 51 if(size[c[x][0]]+1==k)return x; 52 else if(size[c[x][0]]+1>k)return find(c[x][0],k); 53 else return find(c[x][1],k-size[c[x][0]]-1); 54 } 55 void query(int l,int r) 56 { 57 int x=find(rt,l),y=find(rt,r+2); 58 splay(x,rt);splay(y,c[x][1]); 59 int z=c[y][0]; 60 printf("%d\n",mx[z]); 61 return; 62 } 63 void rever(int l,int r) 64 { 65 int x=find(rt,l),y=find(rt,r+2); 66 splay(x,rt);splay(y,c[x][1]); 67 int z=c[y][0]; 68 rev[z]^=1; 69 return; 70 } 71 void add(int l,int r,int ww) 72 { 73 int x=find(rt,l);int y=find(rt,r+2); 74 splay(x,rt);splay(y,c[x][1]); 75 int z=c[y][0]; 76 lz[z]+=ww;mx[z]+=ww;w[z]+=ww; 77 return; 78 } 79 void build(int l,int r,int f){ 80 if(l>r)return; 81 int mid=l+r>>1; 82 fa[mid]=f;c[f][mid>=f]=mid; 83 if(l==r) 84 { 85 w[mid]=0;lz[mid]=0;rev[mid]=0;size[mid]=1;return; 86 } 87 build(l,mid-1,mid);build(mid+1,r,mid); 88 pushdown(mid); 89 return; 90 } 91 int main() 92 { 93 scanf("%d%d",&n,&m);int f,l,r,ww; 94 build(1,n+2,0);rt=(n+3)>>1;mx[0]=-1e9; 95 for(int i=1;i<=m;++i) 96 { 97 scanf("%d",&f); 98 if(f==1) 99 {100 scanf("%d%d%d",&l,&r,&ww);101 add(l,r,ww);102 }103 else if(f==2)104 {105 scanf("%d%d",&l,&r);106 rever(l,r);107 }108 else109 {110 scanf("%d%d",&l,&r);111 query(l,r);112 }113 }114 return 0;115 }