#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int maxn=520007;
int i,j,k,l,n,m,ans,root,posi;
int f[maxn],a[maxn],d[maxn],b[maxn],x,y,key[maxn],shan[maxn],num,zhi,tt[maxn][2];
char s[20];
struct node{
int mx,sum,size,lda,rda,biao,add;
}t[maxn];
void update(int x)
{
if(!x)return;
t[x].size=1+t[tt[x][0]].size+t[tt[x][1]].size;
t[x].sum=key[x]+t[tt[x][0]].sum+t[tt[x][1]].sum;
t[x].lda=max(t[tt[x][0]].lda,t[tt[x][0]].sum+key[x]+t[tt[x][1]].lda);
t[x].rda=max(t[tt[x][1]].rda,t[tt[x][1]].sum+key[x]+t[tt[x][0]].rda);
t[x].mx=max(max(t[tt[x][0]].mx,t[tt[x][1]].mx),t[tt[x][0]].rda+t[tt[x][1]].lda+key[x]);
}
void makesame(int x,int y)
{
if(!x)return;
t[x].sum=t[x].size*y;
key[x]=y;
t[x].add=y;
if(y>0)
t[x].lda=t[x].rda=t[x].mx=t[x].sum;
else
t[x].lda=t[x].rda=0,t[x].mx=y;
}
bool son(int x)
{
if(tt[f[x]][0]==x)return 0;return 1;
}
void rotate(int x)
{
int y=f[x],z=son(x);
tt[y][z]=tt[x][1-z];
if(tt[x][1-z])
f[tt[x][1-z]]=y;
f[x]=f[y];
if(f[y])
tt[f[y]][son(y)]=x;
f[y]=x;
tt[x][1-z]=y;
update(y);update(x);
}
void overturn(int x){
if(!x)return;
swap(tt[x][0],tt[x][1]);
swap(t[x].lda,t[x].rda);
t[x].biao^=1;
}
void down(int x)
{
if(!x)return;
if(t[x].biao)
{
overturn(tt[x][0]);
overturn(tt[x][1]);
t[x].biao=0;
}
if(t[x].add!=maxn)
{
makesame(tt[x][0],t[x].add);
makesame(tt[x][1],t[x].add);
t[x].add=maxn;
}
}
void remove(int x,int y)
{
do{
d[++d[0]]=x;
x=f[x];
}while(x!=y);
while(d[0])down(d[d[0]--]);
}
int insert(int x)
{
int o;
if(shan[0])
o=shan[shan[0]--];
else
o=++num;
key[o]=t[o].sum=t[o].mx=x;
t[o].size=1;
t[o].lda=t[o].rda=max(0,x);
f[o]=t[o].biao=tt[o][0]=tt[o][1]=0;
t[o].add=maxn;
return o;
}
void splay(int x,int y)
{
if(x==y)return;
remove(x,y);
while(f[x]!=y)
{
if(f[f[x]]!=y)
if(son(f[x])==son(x))
rotate(f[x]);
else
rotate(x);
rotate(x);
}
if(!y)
root=x;
}
int build(int l,int r,int y)
{
if(l>r)return 0;
int mid=(l+r)/2;
int x=insert(a[mid]);
f[x]=y;
if(l==r)
return x;
tt[x][0]=build(l,mid-1,x);
tt[x][1]=build(mid+1,r,x);
update(x);
return x;
}
int kth(int x,int k)
{
down(x);
if(t[tt[x][0]].size+1==k)return x;
if(t[tt[x][0]].size+1>k)return kth(tt[x][0],k);
else return kth(tt[x][1],k-t[tt[x][0]].size-1);
}
void del(int x)
{
if(!x)return;
shan[++shan[0]]=x;
del(tt[x][0]);del(tt[x][1]);
}
int main(){
// freopen("fan.in","r",stdin);
// freopen("fan.out","w",stdout);
scanf("%d%d",&n,&m);
t[0].mx=-0x7fffffff;
fo(i,1,n)
scanf("%d",&a[i]);
root=build(0,n+1,0);
while(m--)
{
scanf("%s",s);
if(s[0]=='I')
{
scanf("%d%d",&posi,&k);
//在第posi个位置后，加入K个数字
posi++;
fo(i,1,k)
scanf("%d",&a[i]);
x=kth(root,posi);
splay(x,0);
y=kth(root,posi+1);
splay(y,x);
tt[y][0]=build(1,k,y);
update(y); //更新y结点的信息，因为在y的左子树加了一堆点了
update(x); //更新x结点的信息
}
else if(s[0]=='D')
//从第posi个位置开始，删除K个元素
{
scanf("%d%d",&posi,&k);posi++;
x=kth(root,posi-1);splay(x,0);
y=kth(root,posi+k);splay(y,x);
del(tt[y][0]);
tt[y][0]=0;
update(y);
update(x);
}
else if(s[2]=='K')
//连续K个数字，值改为某个固定值
{
scanf("%d%d%d",&posi,&k,&zhi);posi++;
x=kth(root,posi-1);splay(x,0);
y=kth(root,posi+k);splay(y,x);
makesame(tt[y][0],zhi);
update(y);
update(x);
}
else if(s[0]=='R')
//从第posi个数字开始，翻转其后的K个数字
{
scanf("%d%d",&posi,&k);posi++;
x=kth(root,posi-1);splay(x,0);
y=kth(root,posi+k);splay(y,x);
overturn(tt[y][0]);
update(y);
update(x);
}
else if(s[0]=='G')
//从第posi个数字开始，K个数字之和
{
scanf("%d%d",&posi,&k);posi++;
x=kth(root,posi-1);splay(x,0);
y=kth(root,posi+k);splay(y,x);
printf("%d
",t[tt[y][0]].sum);
}
else
{
x=kth(root,1);splay(x,0);
y=kth(root,t[root].size);splay(y,x);
printf("%d
",t[tt[y][0]].mx);
}
}
}
Poj3580
#include <bits/stdc++.h>
using namespace std;
#define N 510000
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define which(x) (ch[fa[x]][1]==x)
#define inf 0xfffffff
int n,m,cnt,root,lp,rp;
char s[11];
int ch[N][2],a[N];
int val[N],ad[N],size[N],rev[N],mn[N],fa[N];
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
void update(int x)
{
mn[x]=min(mn[ls(x)],mn[rs(x)]);
mn[x]=min(mn[x],val[x]);
size[x]=size[ls(x)]+size[rs(x)]+1;
}
int build(int l,int r)
{
if(l>r)return 0;
int mid=(l+r)>>1,now=++cnt;
if(mid==0||mid==n+1)val[now]=inf;
else val[now]=a[mid];
size[now]=1;
ls(now)=build(l,mid-1);
rs(now)=build(mid+1,r);
fa[ls(now)]=fa[rs(now)]=now;
update(now);
return now;
}
void reverse(int x)
{
swap(ls(x),rs(x));
rev[x]^=1;
}
void add(int x,int v)
{
ad[x]+=v;
if(mn[x]!=inf) mn[x]+=v;
if(val[x]!=inf) val[x]+=v;
}
void pushdown(int x)
{
if(rev[x])
{
reverse(ls(x));
reverse(rs(x));
rev[x]^=1;
}
if(ad[x])
{
add(ls(x),ad[x]);
add(rs(x),ad[x]);
ad[x]=0;
}
}
void down(int x)
{
if(fa[x]) down(fa[x]);
pushdown(x);
}
void rotate(int x)
{
int y=fa[x],k=which(x);
ch[y][k]=ch[x][k^1],ch[x][k^1]=y;
ch[fa[y]][which(y)]=x;
fa[x]=fa[y];fa[y]=x;
fa[ch[y][k]]=y;
update(y);update(x);
}
void splay(int x,int tar)
{
down(x);
while(fa[x]!=tar)
{
int y=fa[x];
if(fa[y]==tar)rotate(x);
else
{
if(which(x)^which(y))
rotate(x);
else rotate(y);
rotate(x);
}
}
if(tar==0)root=x;
}
int Rank(int x,int k)
{
pushdown(x);
if(size[ls(x)]+1==k) return x;
if(size[ls(x)]+1>k) return Rank(ls(x),k);
return Rank(rs(x),k-size[ls(x)]-1);
}
int get(int l,int r)
{
lp=Rank(root,l),rp=Rank(root,r);
splay(lp,0),splay(rp,lp);
return ls(rp);
}
int main()
{
read(n),mn[0]=inf;
for(int i=1;i<=n;i++) read(a[i]);
root=build(0,n+1);
read(m);
int x,y,T;
while(m--)
{
scanf("%s",s+1);
if(s[1]=='A')
{
read(x),read(y),read(T),x++,y++;
add(get(x-1,y+1),T);
}
else if(s[1]=='I')
{
read(x),read(y);x++;
get(x,x+1);
ch[rp][0]=++cnt;fa[cnt]=rp;
size[cnt]=1;val[cnt]=mn[cnt]=y;
update(rp);update(lp);
}
else if(s[1]=='M')
{
read(x),read(y);x++,y++;
printf("%d
",mn[get(x-1,y+1)]);
}
else if(s[1]=='D')
{
read(x),x++;
get(x-1,x+1);ls(rp)=0;
update(lp),update(rp);
}
else if(s[4]=='E')
{
read(x),read(y),x++,y++;
reverse(get(x-1,y+1));
}
else
{
read(x),read(y),read(T),x++,y++;
T=(T%(y-x+1)+y-x+1)%(y-x+1);
if(!T) continue;
int p1=Rank(root,y),p2=Rank(root,y+1);
int t=get(x-1,y-T+1);
down(t);ch[rp][0]=0;
update(rp),update(lp);
splay(p1,0),splay(p2,p1);
down(p2);ch[p2][0]=t,fa[t]=p2;
update(p2),update(p1);
}
}
}