5.19 * 1
/*1.AC:return find(l,rk);
WA:return(l,rk);
*/
#include<iostream>
#include<cstdio>
#define inf 0x7fffffff
#define N 50001
using namespace std;
int n,m,rt,sz,c[N][2],mark[N],fa[N],v[N],size[N],mx[N],tag[N];
bool rev[N];
void update(int k){
int l=c[k][0],r=c[k][1];
mx[k]=max(mx[l],mx[r]);
mx[k]=max(mx[k],v[k]);
size[k]=size[l]+size[r]+1;
}
void rotate(int x,int &k){
int y=fa[x],z=fa[y],l,r;
if(c[y][0]==x)l=0;else l=1;r=l^1;
if(y==k)k=x;
else{
if(c[z][0]==y)c[z][0]=x;
else c[z][1]=x;
}
fa[y]=x;fa[x]=z;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
update(x);update(y);
}
void splay(int x,int &k){
int y,z;
while(x!=k){
y=fa[x];z=fa[y];
if(y!=k){
if((c[y][0]==x)^(c[z][0]==y))rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
void build(int l,int r,int last){
if(l>r)return;
if(l==r){
size[mark[l]]=1;fa[mark[l]]=mark[last];
if(l<last)c[mark[last]][0]=mark[l];
else c[mark[last]][1]=mark[l];
return;
}
int mid=(l+r)>>1;
build(l,mid-1,mid);build(mid+1,r,mid);
fa[mark[mid]]=mark[last];
update(mark[mid]);
if(mid<last)c[mark[last]][0]=mark[mid];
else c[mark[last]][1]=mark[mid];
}
void pushdown(int x){
int y=c[x][0],z=c[x][1],t=tag[x];
if(t!=0){
if(y){v[y]+=t;mx[y]+=t;tag[y]+=t;}
if(z){v[z]+=t;mx[z]+=t;tag[z]+=t;}
tag[x]=0;
}
if(rev[x]){
swap(c[x][0],c[x][1]);
if(y)rev[y]^=1;
if(z)rev[z]^=1;
rev[x]=0;
}
}
int find(int k,int rk){
if(tag[k]||rev[k])pushdown(k);
int l=c[k][0],r=c[k][1];
if(size[l]+1==rk)return k;
else if(size[l]>=rk)return find(l,rk);
else return find(r,rk-size[l]-1);
}
void add(int l,int r,int w){
int x=find(rt,l),y=find(rt,r+2);
splay(x,rt);splay(y,c[x][1]);
int z=c[y][0];
v[z]+=w;mx[z]+=w;tag[z]+=w;
update(x);update(y);
}
void rever(int l,int r){
int x=find(rt,l),y=find(rt,r+2);
splay(x,rt);splay(y,c[x][1]);
int z=c[y][0];
rev[z]^=1;
}
void ask(int l,int r){
int x=find(rt,l),y=find(rt,r+2);
splay(x,rt);splay(y,c[x][1]);
int z=c[y][0];
printf("%d\n",mx[z]);
}
int main(){
mx[0]=-inf;
scanf("%d%d",&n,&m);
for(int i=1;i<=n+2;i++)mark[i]=++sz;
build(1,n+2,0);
rt=(n+3)>>1;
for(int i=1;i<=m;i++){
int t,l,r,x;
scanf("%d",&t);
switch(t){
case 1:scanf("%d%d%d",&l,&r,&x);add(l,r,x);break;
case 2:scanf("%d%d",&l,&r);rever(l,r);break;
case 3:scanf("%d%d",&l,&r);ask(l,r);break;
}
}
return 0;
}
7.28 * 1 (1A)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
#define inf 0x7fffffff
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N=50001;
int n,m,rt,sz,c[N][2],mark[N],fa[N],v[N],size[N],mx[N],tag[N];
bool rev[N];
inline void update(int k){
int l=c[k][0],r=c[k][1];
mx[k]=max(max(mx[l],mx[r]),v[k]);
size[k]=size[l]+size[r]+1;
}
inline void rotate(int x,int &k){
int y=fa[x],z=fa[y],l,r;
if(c[y][0]==x)l=0;else l=1;r=l^1;
if(y==k)k=x;
else{
if(c[z][0]==y)c[z][0]=x;
else c[z][1]=x;
}
fa[y]=x;fa[x]=z;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
update(x);update(y);
}
inline void splay(int x,int &k){
int y,z;
while(x!=k){
y=fa[x];z=fa[y];
if(y!=k){
if((c[y][0]==x)^(c[z][0]==y))rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
inline void build(int l,int r,int last){
if(l>r)return;
if(l==r){
size[mark[l]]=1;fa[mark[l]]=mark[last];
if(l<last)c[mark[last]][0]=mark[l];
else c[mark[last]][1]=mark[l];
return;
}
int mid=(l+r)>>1;
build(l,mid-1,mid);build(mid+1,r,mid);
fa[mark[mid]]=mark[last];
update(mark[mid]);
if(mid<last)c[mark[last]][0]=mark[mid];
else c[mark[last]][1]=mark[mid];
}
inline void pushdown(int k){
int l=c[k][0],r=c[k][1],t=tag[k];
if(t){
if(l){v[l]+=t;mx[l]+=t;tag[l]+=t;}
if(r){v[r]+=t;mx[r]+=t;tag[r]+=t;}
tag[k]=0;
}
if(rev[k]){
swap(c[k][0],c[k][1]);
if(l)rev[l]^=1;
if(r)rev[r]^=1;
rev[k]=0;
}
}
inline int find(int k,int rk){
if(tag[k]||rev[k])pushdown(k);
int l=c[k][0],r=c[k][1];
if(size[l]+1==rk)return k;
else if(size[l]>=rk)return find(l,rk);
else return find(r,rk-size[l]-1);
}
inline void add(int l,int r,int w){
int x=find(rt,l),y=find(rt,r+2);
splay(x,rt);splay(y,c[x][1]);
int z=c[y][0];
v[z]+=w;mx[z]+=w;tag[z]+=w;
update(x);update(y);
}
inline void rever(int l,int r){
int x=find(rt,l),y=find(rt,r+2);
splay(x,rt);splay(y,c[x][1]);
int z=c[y][0];
rev[z]^=1;
}
inline void ask(int l,int r){
int x=find(rt,l),y=find(rt,r+2);
splay(x,rt);splay(y,c[x][1]);
int z=c[y][0];
printf("%d\n",mx[z]);
}
int main(){
mx[0]=-inf;
scanf("%d%d",&n,&m);
for(int i=1;i<=n+2;i++)mark[i]=++sz;
build(1,n+2,0);
rt=(n+3)>>1;
for(int i=1;i<=m;i++){
int t,l,r,x;
scanf("%d",&t);
switch(t){
case 1:scanf("%d%d%d",&l,&r,&x);add(l,r,x);break;
case 2:scanf("%d%d",&l,&r);rever(l,r);break;
case 3:scanf("%d%d",&l,&r);ask(l,r);break;
}
}
return 0;
}