【*】POJ-3580(ストレッチツリー-slpay tree)

ツリーを伸ばすメリット:
Splay Treeは絶えず調整されるだけで、追加のタグは導入されていないため、ツリー構造は標準BSTと何の違いもなく、空間的な観点からTreap、Red-Black Tree、AVLよりもずっと効率的である.構造は変わらないので、左回転と右回転による操作であればSplay Treeの性質に影響を及ぼさないため、BSTの中でも最も豊富な機能を提供している.迅速な分割とマージ(ここでは、元のツリーを2本のツリーに分割することを意味し、1本のツリーのすべてのノードが他のツリーよりも小さく、逆のプロセスを指す)を含み、実現が極めて便利である.これは他の構造では実現しにくい.その時間効率もかなり安定しており、Treapとほぼ同等である.

/*==========================================================*\
|    （splay tree）
|     ： 
|	(1)           value 
|	(2)       
|	(3)         k (            ) 
|	(4)       
|	(5)       
|	(6)          
\*==========================================================*/
#define type int
#define MAXN 2000005
#define MAXL 100005
#define INF (1<<30)
struct Splay_Tree
{
    struct Node//  
    {
        Node *c[2],*p;
        int value,size,Min,lazy;
        bool rev;
    }*root,*null,*lb,*rb,S[MAXN];
    int scnt;
    //inline int max(int a,int b) {return a>b?a:b;}
    inline Node * NewNode(int value,Node *p)//     
    {
        Node *e=S+(++scnt);
        e->value=value;
        e->size=1;
        e->p=p;
        e->Min=value;
        e->lazy=0;
        e->rev=false;
        e->c[0]=e->c[1]=null;
        return e;
    }
    inline void Update(Node *p)//      
	{
		if (p==null) return;
		p->size=p->c[0]->size+p->c[1]->size+1;
		p->Min=MY_MIN(p->value,MY_MIN(p->c[0]->Min,p->c[1]->Min));
	}
    inline void PushDown(Node *x)//    
    {
        if(x==null) return;
        if(x->rev)
        {
            x->rev=false;
            Node *t=x->c[0]; x->c[0]=x->c[1]; x->c[1]=t;
            x->c[0]->rev=!x->c[0]->rev;
            x->c[1]->rev=!x->c[1]->rev;
            //int w=x->ll; x->ll=x->rr; x->rr=w;
        }
        if(x->lazy)
        {
            int w=x->lazy;
            x->value+=w;
            x->Min+=w;
            x->c[0]->lazy+=w;
            x->c[1]->lazy+=w;
            x->lazy=0;
        }
    }
    inline void Rotate(Node *x,int k)//   k=0；   k=1；
    {
        Node *y=x->p;
        PushDown(x->c[0]);
        PushDown(x->c[1]);
        PushDown(y->c[!k]);
        y->c[k]=x->c[!k];
        y->c[k]->p=y;
        x->p=y->p;
        if(y->p->c[0]==y)
            y->p->c[0]=x;
        else
            y->p->c[1]=x;
        y->p=x;
        x->c[!k]=y;
        Update(y);
        Update(x);
        if(root==y) root=x;
    }
    inline void Splay(Node *x,Node *y)//  
    {
        PushDown(x);
        while(x->p!=y)
        {
            if(x->p->p==y)
            {
                if(x->p->c[0]==x)
                    Rotate(x,0);
                else
                    Rotate(x,1);
            }
            else if(x->p->p->c[0]==x->p)
            {
                if(x->p->c[0]==x)
                    Rotate(x->p,0),Rotate(x,0);
                else
                    Rotate(x,1),Rotate(x,0);
            }
            else
            {
                if(x->p->c[1]==x)
                    Rotate(x->p,1),Rotate(x,1);
                else
                    Rotate(x,0),Rotate(x,1);
            }
        }
        Update(x);
    }
    inline void Select(int k,Node *y)
    {
        Node *x=root;
        PushDown(x);
        while(k!=x->c[0]->size+1)
        {
            if(k<=x->c[0]->size)
                x=x->c[0];
            else
            {
                k-=x->c[0]->size+1;
                x=x->c[1];
            }
            PushDown(x);
        }
		Splay(x,y);
    }
    inline void MakeTree(int l,int r,type C[],Node *p,int side)
    {
        if(l>r) return;
        int mid=(l+r)>>1;
        Node *x;
        x=NewNode(C[mid],p);
        p->c[side]=x;
        MakeTree(l,mid-1,C,x,0);
        MakeTree(mid+1,r,C,x,1);
        Update(x);
    }
    inline void Insert(int pos,int cnt,type C[])// pos      cnt   
    {
        Select(pos+1,null);
        Select(pos+2,root);
        MakeTree(1,cnt,C,root->c[1],0);
        Splay(root->c[1]->c[0],null);
    }
    inline void Add(int pos,int cnt,type value)// pos    cnt           value
    {
        Select(pos,null);
        Select(pos+cnt+1,root);
        root->c[1]->c[0]->lazy+=value;
        Splay(root->c[1]->c[0],null);
    }
    inline void Delete(int pos,int cnt)//  pos    cnt   
    {
        Select(pos,null);
        Select(pos+cnt+1,root);
        root->c[1]->c[0]=null;
        Splay(root->c[1],null);
    }
    inline void Reverse(int pos,int cnt)//  pos    cnt   
    {
        Select(pos,null);
        Select(pos+cnt+1,root);
        root->c[1]->c[0]->rev=!root->c[1]->c[0]->rev;
        Splay(root->c[1]->c[0],null);
    }
    inline void Revolve(int a,int b,int k)// [a,b]      k 
    {
        int len=(b-a+1),A,B,C;
        k=((k%len)+len)%len;
        if(k==0) return;
        
        A=a;B=b-k;C=b;                  //       [A,B],[B+1,C];
        Node *p1,*p2,*p3,*p4;
        
        Select(A,null); p1=root;        //A-1;
        Select(C+2,null); p2=root;      //C+1;
        Select(A+1,null); p3=root;      //A;
        Select(B+1,null); p4=root;      //B;
        
        Select(A,null);                 // A-1   root
        Select(C+2,p1);                 // C+1   A-1   
        Select(B+1,p2);                 // B   C+1   
        Node *x,*y;
        
        x=p4->c[1];                     // b      ，  a   
        p4->c[1]=null;
        
        p3->c[0]=x;
        Splay(p3,null);                 // a   root,      
    }
    inline type GetMin(int pos,int cnt)//  pos    cnt       
    {
        Select(pos,null);
        Select(pos+cnt+1,root);
        PushDown(root->c[1]->c[0]);
        return root->c[1]->c[0]->Min;
    }
    void Index(int pos)
    {
        Select(pos+1,null);
        printf("*%d
",root->value);
    }
    inline void Print()//    
    {
        int i;
        for(i=1;i<scnt-1;i++)
            Index(i);
    }
    inline void Init()
    {
        scnt=-1;
        null=0;
        null=NewNode(INF,0);
        null->size=0;
		lb=root=NewNode(INF,null);
        rb=root->c[1]=NewNode(INF,root);
        Update(root);
    }
}Splay;
int N,M,pos;
type C[MAXL],ans;
char s[20];
int main()
{
    int i,j,a,b,c,k;
    Splay.Init();
    scanf("%d",&N);
    for(i=1;i<=N;i++)
        scanf("%d",&C[i]);
        
    //printf("*
");
    //Stop;
    Splay.Insert(0,N,C);

    //Splay.Print();

    scanf("%d",&M);
    while(M--)
    {
        scanf("%s",s);
        if(s[0]=='A')
        {
            scanf("%d%d%d",&a,&b,&c);
            Splay.Add(a,b-a+1,c);
        }
        else if(s[0]=='R')
        {
            scanf("%d%d",&a,&b);
            if(s[3]=='E')
                Splay.Reverse(a,b-a+1);
            else
            {
                scanf("%d",&k);
                Splay.Revolve(a,b,k);
                //Splay.Print();
            }
        }
        else if(s[0]=='I')
        {
            scanf("%d%d",&a,&C[1]);
            Splay.Insert(a,1,C);
        }
        else if(s[0]=='D')
        {
            scanf("%d",&a);
            Splay.Delete(a,1);
        }
        else
        {
            scanf("%d%d",&a,&b);
            ans=Splay.GetMin(a,b-a+1);
            printf("%d
",ans);
        }
    }
	return 0;
}