POJ 3580 SuperMemo（splay）

题目链接：http://poj/problem?id=3580

题意：一个数列，6种操作：

（1）将[L,R]之间的数字都加d；

（2）将[L,R]之间的数字翻转；

（3）将[L,R]之间的数字向右循环d次；

（4）在pos位置插入数字d；

（5）删掉pos位置的数字；

（6）输出[L,R]的最小值。

思路：第一第二种操作在节点上增加标记；第三种操作等价于将[A,B],[B+1,C]两个区间的数字交换。首先将A-1和C+1调整到根节点和根节点的右子树，则[A,C]区间就在根节点右子树的左子树上。接着将B调整到根节点右子树的左子树P，则[A,B-1]在P的左子树L，[B+1,C]在P的右子树R，最后将R截下放在L的左子树。第四将pos调整到根节点，将pos+1调整到根节点的右子树，则插入位置为根节点右子树的左子树；删除时将pos调整到根节点，pos+2调整到根节点右子树，则pos到了根节点右子树的左子树直接删掉即可；最小值在节点上增加一个记录即可。

struct node
{
    int Min,value,rev,lazy,size;
    node* c[2];
    node* p;
};

node a[N],*root,*null;
int n,m,b[N],cnt;

node* newNode(int value,node *p)
{
    node *e=a+(cnt++);
    e->value=value;
    e->size=1;
    e->p=p;
    e->Min=value;
    e->lazy=e->rev=0;
    e->c[0]=e->c[1]=null;
    return e;
}



void pushDown(node *p)
{
    if(p==null) return;
    if(p->rev)
    {
        p->rev=0;
        swap(p->c[0],p->c[1]);
        p->c[0]->rev^=1;
        p->c[1]->rev^=1;
    }
    if(p->lazy)
    {
        p->value+=p->lazy;
        p->Min+=p->lazy;
        p->c[0]->lazy+=p->lazy;
        p->c[1]->lazy+=p->lazy;
        p->lazy=0;
    }
}



void pushUp(node *p)
{
    if(p==null) return;
    p->size=p->c[0]->size+p->c[1]->size+1;
    p->Min=min(p->value,min(p->c[0]->Min,p->c[1]->Min));
}

void init()
{
    cnt=0;
    null=0;
    null=newNode(INF,0);
    null->size=0;
    root=newNode(INF,null);
    root->c[1]=newNode(INF,root);
    pushUp(root);
}

void rotate(node *x,int k)
{
    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;
    pushUp(y);
    pushUp(x);
    if(root==y) root=x;
}



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);
            else rotate(x,1);
            rotate(x,0);
        }
        else
        {
            if(x->p->c[1]==x) rotate(x->p,1);
            else rotate(x,0);
            rotate(x,1);
        }
    }
}


void select(int k,node *y)
{
    node *x=root;
    pushDown(x);
    while(k!=x->c[0]->size+1)
    {
        if(k<x->c[0]->size+1) x=x->c[0];
        else
        {
            k-=x->c[0]->size+1;
            x=x->c[1];
        }
        pushDown(x);
    }
    splay(x,y);
}

void build(int L,int R,int b[],node *p,int side)
{
    if(L>R) return;
    int mid=(L+R)>>1;
    node *x=newNode(b[mid],p);
    p->c[side]=x;
    build(L,mid-1,b,x,0);
    build(mid+1,R,b,x,1);
    pushUp(x);
}


void insert(int pos,int cnt,int b[])
{
    select(pos+1,null);
    select(pos+2,root);
    build(1,cnt,b,root->c[1],0);
    splay(root->c[1]->c[0],null);
}

void add(int pos,int cnt,int det)
{
    select(pos,null);
    select(pos+cnt+1,root);
    root->c[1]->c[0]->lazy+=det;
    splay(root->c[1]->c[0],null);
}

void del(int pos,int cnt)
{
    select(pos,null);
    select(pos+cnt+1,root);
    root->c[1]->c[0]=null;
    splay(root->c[1],null);
}


void reverse(int pos,int cnt)
{
    select(pos,null);
    select(pos+cnt+1,root);
    root->c[1]->c[0]->rev^=1;
    splay(root->c[1]->c[0],null);
}

void revolve(int L,int R,int k)
{
    int len=R-L+1,A,B,C;
    k%=len;
    if(!k) return;
    A=L+1;B=R-k+1;C=R+1;
    node *p1,*p2,*p3,*p4;
    select(A-1,null);  p1=root;
    select(C+1,null);  p2=root;
    select(A,null);    p3=root;
    select(B,null);    p4=root;

    select(A-1,null);
    select(C+1,p1);
    select(B,p2);

    p3->c[0]=p4->c[1];
    p4->c[1]=null;
    splay(p3,null);
}

int getMin(int pos,int cnt)
{
    select(pos,null);
    select(pos+cnt+1,root);
    return root->c[1]->c[0]->Min;
}



int main()
{
    init();
    scanf("%d",&n);
    int i,x,y,z;
    char op[15];
    for(i=1;i<=n;i++) scanf("%d",b+i);
    insert(0,n,b);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",op);
        if(op[0]=='A')
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y-x+1,z);
        }
        else if(op[0]=='R'&&op[3]=='E')
        {
            scanf("%d%d",&x,&y);
            reverse(x,y-x+1);
        }
        else if(op[0]=='R'&&op[3]=='O')
        {
            scanf("%d%d%d",&x,&y,&z);
            revolve(x,y,z);
        }
        else if(op[0]=='I')
        {
            scanf("%d%d",&x,&b[1]);
            insert(x,1,b);
        }
        else if(op[0]=='D')
        {
            scanf("%d",&x);
            del(x,1);
        }
        else
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",getMin(x,y-x+1));
        }
    }
    return 0;
}