POJ 3580

題意:配列を与えて、6種類の操作があります.
add x y d:[x,y]のすべての数にdを加算
reverse x y:[x,y]区間反転
revolve x y t:[x,y]サイクル右シフトtビット、tは任意の整数をとることができる
insert x v:x番目の位置にvの値を挿入する数
delete x:x番目の数を削除
min x y:区間[x,y]の最小値を求める
問題解:典型的なsplayは、処理する区間をrootの右の子供の左の木に回転させ、すべての操作をこの上で処理します.
add/reverse:直接タグ処理が可能で、次回の回転時に下伝タグで解決
revolve:右端にt個のノードを含むサブツリーを左端に接ぎ木すると見なす
Insert:挿入する位置をルートノードに移動し、次のノードをルートノードの右の子供に移動することで、この2つのノード間に直接ノードを追加することで解決できます.
delete:xの位置をルートノードに、xの位置をルートノードの右の子供に、左の子供を削除します.
これは私の最初のsplayで、論文を見るのに半日かかって、書くのに半日かかって、デバッグは1日使って、reは無数で、waは1回、繰り返して最適化して、最後にやっと1秒に入りました.回転操作だけでsplayを見ると、確かに水構造ですが、いろいろな反転があって、交代が重なっても卵が痛くなります.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef struct sp_node * Node;
const int MAXN=210010,inf=100000000;
struct sp_node
{
    Node pre,ch[2];
    int value,lazy,Min,size;//    ，lazy  ，     ，    
    bool rev;//    
    void init(int _value)
    {
        pre=ch[0]=ch[1]=NULL;
        Min=value=_value;
        lazy=0;
        size=1;
        rev=false;
    }
} nstack[MAXN];
int scnt;//    splay       
Node root;
inline int getsize(Node &x)//  x    ，     x=NULL   
{
    return x?x->size:0;
}
void pushdown(Node &x)// x    
{
    if(!x)
        return;
    if(x->lazy)
    {
        int w=x->lazy;
        x->value+=w;
        if(x->ch[0])
        {
            x->ch[0]->lazy+=w;
            x->ch[0]->Min+=w;
        }
        if(x->ch[1])
        {
            x->ch[1]->lazy+=w;
            x->ch[1]->Min+=w;
        }
        x->lazy=0;
    }
    if(x->rev)
    {
        Node t=x->ch[0];
        x->ch[0]=x->ch[1];
        x->ch[1]=t;
        x->rev=false;
        if(x->ch[0])
            x->ch[0]->rev^=1;
        if(x->ch[1])
            x->ch[1]->rev^=1;
    }
}
void updata(Node &x)//  x    
{
    if(!x)
        return;
    x->size=1;
    x->Min=x->value;
    if(x->ch[0])
    {
        x->Min=min(x->Min,x->ch[0]->Min);
        x->size+=x->ch[0]->size;
    }
    if(x->ch[1])
    {
        x->Min=min(x->Min,x->ch[1]->Min);
        x->size+=x->ch[1]->size;
    }
}
void rotate(Node &x, int d) //     ，d=0     ，d=1     
{
    Node y=x->pre;
    pushdown(y);
    pushdown(x);
    pushdown(x->ch[d]);
    y->ch[!d]=x->ch[d];
    if (x->ch[d]!=NULL) x->ch[d]->pre=y;
    x->pre = y->pre;
    if (y->pre!=NULL)
    {
        if (y->pre->ch[0]==y) y->pre->ch[0]=x;
        else y->pre->ch[1]=x;
    }
    x->ch[d]=y,y->pre=x;
    updata(y);
    if (y == root)//     ，  root       
        root = x;
}
void splay(Node &x, Node &f) // Splay   ，     x     f
{
    for (pushdown(x); x!=f;)
    {
        if(x->pre==f)
        {
            if(f->ch[0]==x)
                rotate(x,1);
            else
                rotate(x,0);
            break;
        }
        else
        {
            Node y=x->pre,z=y->pre;
            if (z->ch[0] == y)
                if (y->ch[0] == x)
                    rotate(y,1),rotate(x, 1); //      
                else
                    rotate(x, 0), rotate(x, 1); //      
            else if (y->ch[1] == x)
                rotate(y, 0), rotate(x, 0); //      
            else
                rotate(x, 1), rotate(x, 0); //      
            if(z==f)//    ，x     z   ，  z       ，      
                break;
        }
        updata(x);
    }
    updata(x);
}
void select(int k, Node &f)
{
    int tmp;
    Node t;
    for(t=root;;)
    {
        pushdown(t);
        tmp=getsize(t->ch[0]); //   t       
        if (k == tmp + 1) break; //   t       ，    
        if (k <= tmp) //  k     t   ，   
            t = t->ch[0];
        else //      ，       ，        k  
            k -=tmp+1,t=t->ch[1];
    }
    pushdown(t);
    splay(t, f); //     
}
void insert(int pos,int value)
{
    select(pos+1,root);
    select(pos+2,root->ch[1]);
    Node t=nstack+scnt++,x=root->ch[1];
    pushdown(root);
    pushdown(x);
    t->init(value);
    t->ch[1]=x;
    x->pre=t;
    root->ch[1]=t;
    t->pre=root;
    splay(x,root);
}
void add(int a,int b,int d)
{
    select(a,root);
    select(b+2,root->ch[1]);
    Node x=root->ch[1]->ch[0];
    pushdown(x);
    updata(x);
    x->Min+=d;
    x->lazy+=d;
    splay(x,root);
}
void reverse(int a,int b)
{
    select(a,root);
    select(b+2,root->ch[1]);
    root->ch[1]->ch[0]->rev^=1;
    Node x=root->ch[1]->ch[0];
    splay(x,root);
}
void revolve(int a,int b,int t)
{
    Node p1,p2;
    select(a,root);
    select(b+2,root->ch[1]);
    select(b+1-t,root->ch[1]->ch[0]);
    p1=root->ch[1]->ch[0];
    pushdown(p1);
    p2=p1->ch[1];
    p1->ch[1]=NULL;
    select(a+1,root->ch[1]->ch[0]);
    p1=root->ch[1]->ch[0];
    pushdown(p1);
    p1->ch[0]=p2;
    p2->pre=p1;
    splay(p2,root);
}
int getmin(int a,int b)
{
    select(a,root);
    select(b+2,root->ch[1]);
    Node x=root->ch[1];
    pushdown(x);
    x=x->ch[0];
    pushdown(x);
    updata(x);
    return x->Min;
}
void erase(int pos)
{
    select(pos,root);
    select(pos+2,root->ch[1]);
    pushdown(root->ch[1]);
    root->ch[1]->ch[0]=NULL;
    Node x=root->ch[1];
    splay(x,root);
}
int main()
{
    int i,a,b,c,k,n,m;
    scnt=0;
    root=nstack+scnt++;
    root->init(inf);
    root->ch[1]=nstack+scnt++;
    root->ch[1]->init(inf);
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&c);
        insert(i,c);
    }
    scanf("%d",&m);
    while(m--)
    {
        char s[50];
        scanf("%s", s);
        if(s[0]=='A')
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        else if(s[0]=='R')
        {
            scanf("%d%d",&a,&b);
            if(s[3]=='E')
                reverse(a,b);
            else
            {
                scanf("%d",&k);
                int tn=b-a+1;
                k=(k%tn+tn)%tn;
                if(a==b||k==0)
                    continue;
                revolve(a,b,k);
            }
        }
        else if(s[0]=='I')
        {
            scanf("%d%d",&a,&c);
            insert(a,c);
        }
        else if(s[0]=='D')
        {
            scanf("%d",&a);
            erase(a);
        }
        else
        {
            scanf("%d%d",&a,&b);
            int ans=getmin(a,b);
            printf("%d
",ans);
        }
    }
    return 0;
}