看心情填坑

http://poj.org/problem?id=3580

神TM的SPLAY模板题

SPLAY的两种应用，一种维护集合，一种维护数列，这道作为维护数列的入门题不管怎么说也是要比文艺平衡树好的。

维护区间加，区间反转，插入元素，删除元素，区间最小值，REVOLVE操作只要把SPLAY分离之后再合并就行了，都是很基本的东西没什么好讲的，基本只要会线段树以及集合的SPLAY这个就很好写。

前提是你调得出来（括弧笑）

#include<cstdio>
using namespace std;
char s[8];
struct node{
    int fa,r,l,s,num,add,min,re;
}t[200005];
int n,m,l,r,d,root;
void pushup(int k){
    t[k].s=t[t[k].l].s+t[t[k].r].s+1;
	t[k].min=t[k].num;
	if(t[k].l>0)if(t[t[k].l].min<t[k].min)t[k].min=t[t[k].l].min;
	if(t[k].r>0)if(t[t[k].r].min<t[k].min)t[k].min=t[t[k].r].min;
}
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
void pushdown(int k){
	if(t[k].re){
		int tmp=t[k].l;
		t[k].l=t[k].r;
		t[k].r=tmp;
		if(t[k].l>0)t[t[k].l].re^=1;
		if(t[k].r>0)t[t[k].r].re^=1;
		t[k].re=false;
	}
	if(t[k].add==0)return;
	if(t[k].l>0){t[t[k].l].add+=t[k].add;t[t[k].l].min+=t[k].add;t[t[k].l].num+=t[k].add;}
	if(t[k].r>0){t[t[k].r].add+=t[k].add;t[t[k].r].min+=t[k].add;t[t[k].r].num+=t[k].add;}
	t[k].add=0;
}
void rorate(int k,int i){
    int tmp=t[k].fa;
    t[k].fa=t[tmp].fa;
    if(t[t[tmp].fa].l==tmp)t[t[tmp].fa].l=k;
    else t[t[tmp].fa].r=k;
    t[tmp].fa=k;
    if(i==0){
        if(t[k].l>0)t[t[k].l].fa=tmp;
        t[tmp].r=t[k].l;
        t[k].l=tmp;
    }else{
        if(t[k].r>0)t[t[k].r].fa=tmp;
        t[tmp].l=t[k].r;
        t[k].r=tmp;
    }
    pushup(tmp);pushup(k);
}
void splay(int k,int g){
	pushdown(g);
    while(t[k].fa!=g){
        int tmp=t[k].fa;
        if(t[tmp].fa==g){
        	pushdown(tmp);pushdown(k);
			if(t[tmp].r==k)rorate(k,0);
        	else rorate(k,1);
        }
        else{
            int Tmp=t[tmp].fa;
            pushdown(Tmp);pushdown(tmp);pushdown(k);
            if(t[Tmp].l==tmp){
                if(t[tmp].l==k)rorate(tmp,1);
                else rorate(k,0);
                rorate(k,1);
            }else{
                if(t[tmp].r==k)rorate(tmp,0);
                else rorate(k,1);
                rorate(k,0);
            }
        }
    }
    if(g==0)root=k;
}
int find(int x,int roo){
    int k=roo;
    pushdown(k);
    while((t[t[k].l].s+1!=x)){
        if(t[t[k].l].s+1>x)k=t[k].l;
        else x-=t[t[k].l].s+1,k=t[k].r;
        pushdown(k);
    }
    return k;
}
void ins(int x,int y){
	int k=find(x+1,root);
	splay(k,0);
	k=find(x,root);
	splay(k,root);
	n++;
	t[k].r=n;
	t[n].num=t[n].min=y;t[n].fa=k;t[n].s=1;t[n].add=0;
	pushup(k);
	pushup(root);
}
void del(int x){
	int k=find(x-1,root);
	splay(k,0);
	k=find(x+1,root);
	splay(k,root);
	t[t[k].l].s=0;
	t[k].l=0;
	pushup(k);
	pushup(root);
}
int findmin(int x,int y){
	int k=find(x-1,root);
	splay(k,0);
	k=find(y+1,root);
	splay(k,root);
	return t[t[k].l].min;
}
void add(int x,int y,int d){
	int k=find(x-1,root);
	splay(k,0);
	k=find(y+1,root);
	splay(k,root);
	t[t[k].l].add+=d;t[t[k].l].num+=d;t[t[k].l].min+=d;
}
void reve(int x,int y){
	int k=find(x-1,root);
	splay(k,0);
	k=find(y+1,root);
	splay(k,root);
	t[t[k].l].re^=1;
}
void revo(int x,int y,int d){
	int k=find(x-1,root);
	splay(k,0);
	k=find(y+1,root);
	splay(k,root);
	int tmp=find(d,t[k].l);
	splay(tmp,k);
	int Tmp=t[tmp].r;
	pushdown(Tmp);
	while(t[Tmp].r){
		Tmp=t[Tmp].r;
		pushdown(Tmp);
	}
	splay(Tmp,tmp);
	pushdown(Tmp);
	t[Tmp].r=tmp;t[Tmp].fa=k;
	t[tmp].fa=Tmp;t[tmp].r=0;
	t[k].l=Tmp;
	pushup(tmp);
	pushup(Tmp);
}
int main(){
	n=read();
	root=1;
	t[1].fa=0;t[1].s=n+2;t[1].re=false;t[1].min=t[1].num=1000000000;
	for(int i=2;i<=n+1;i++){
		t[i].num=read();
		t[i-1].r=i;
		t[i].fa=i-1;t[i].s=n+3-i;t[i].re=false;
	}
	t[n+2].fa=n+1;t[n+1].r=n+2;t[n+2].s=1;t[n+2].re=false;t[n+2].num=t[n+2].min=1000000000;
	for(int i=n+1;i>0;i--)if(t[i].num>t[i+1].min)t[i].min=t[i+1].min;
	else t[i].min=t[i].num;
	n+=2;
	m=read();
	for(int i=1;i<=m;i++){
		scanf("%s",&s);
		if(s[0]=='A'){
			l=read();r=read();d=read();
			add(l+1,r+1,d);
		}else if(s[0]=='M'){
			l=read();r=read();
			printf("%d\n",findmin(l+1,r+1));
		}else if(s[0]=='D'){
			d=read();
			del(d+1);
		}else if(s[0]=='I'){
			l=read();d=read();
			ins(l+1,d);
		}else if(s[3]=='E'){
			l=read();r=read();
			reve(l+1,r+1);
		}else if(s[3]=='O'){
			l=read();r=read();d=read();
			d%=(r-l+1);
			if(d==0)continue;
			d=r-l+1-d;
			revo(l+1,r+1,d);
		}
	}
}