poj 3580 SuperMemo(伸展樹splay)

伸展樹挺複雜的，而且還有各種版本，這裡找到一種教高效率的版本http://wenku.baidu.com/view/b9cc2c75a417866fb84a8ee4.html

它的意思是在查找節點x的同時就自頂向下地伸展。我寫不出代碼，有些地方還暫時沒看懂,先留着吧。這個代碼是抄網上的，750ms

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N=200010,oo=1<<30;

struct node
{
    #define lc c[0]
    #define rc c[1]
    int w,sz,lz,mn,rev;//w->值,,,sz->size,,,lz->key總量的lazy,,,mn->最小值,,,rev->反轉的lazy
    node *c[2],*f;//左右孩紙和父指針,,f 僅用來splay的回溯up(),,是以不需要時時維護
    void clear(int x);//建立節點指派x,,并清空原值
    void dwn();//下傳
    void up();//上傳
    void add(int x)//權值增加x
    {
        w+=x;
        lz+=x;
        mn+=x;
    }
}te[N],*nil=te,*pe=te,*pt[2],*rt;
//te->樹,,nil->空指針,,其值不變,,pe->目前指針,,,pt->左右鍊,,rt->根

void node::clear(int x)
{
    mn=w=x;
    lc=rc=f=nil;
    sz=1;
    lz=rev=0;
}

void node::dwn()
{
    if (rev)
    {
        swap(lc,rc);
        lc->rev^=1;
        rc->rev^=1;
        rev=0;
    }
    if(lz)
    {
        if (lc!=nil)
            lc->add(lz);
        if (rc!=nil)
            rc->add(lz);
        lz=0;
    }
}

void node::up()//向上更新,,同時含有清空節點的功能
{
    sz=lc->sz+rc->sz+1;
    mn=min(lc->mn,rc->mn);
    mn=min(mn,w);
}

inline void zig(node*&x,int w)//旋轉x和x->c[w];更新x為新的父親
{
    node *y=x->c[w];
    x->c[w]=y->c[!w];
    y->c[!w]=x;
    x->up();
    x=y;//x->up();//這個在finish中有更新,,
}
void finish(node*&x,int w)
{
    pt[w]->c[!w]=x->c[w];//連結
    x->c[w]=nil->c[!w];
    nil->c[!w]->f=x;
    if (pt[w]==nil)
        return;
    for (node *y=pt[w];y!=x;y=y->f)//更新
        y->up();
}
#define cmp(x,y) ((y==x->lc->sz+1)?-1:(y>x->lc->sz))
void splay(node*&x,int k)//将排名第k(x為根的子樹中)的節點提根至x節點
{
    pt[0]=pt[1]=nil;//左右鍊為空
    while(true)
    {
        x->dwn();
        int w=cmp(x,k);
        if (w==-1)//找到k
            break;
        if (w== 1)//右子樹
            k-=x->lc->sz+1;
        x->c[w]->dwn();
        if (w==cmp(x->c[w],k))
        {
            k-=w*(x->c[w]->lc->sz+1);//右子樹,,再減,,
            zig(x,w);//旋轉
        }
        pt[!w]->c[w]=x;//連結
        x->f=pt[!w];
        pt[!w]=x;//更新鍊
        x=x->c[w];//更新mid鍊根
    }
    finish(x,0);//連接配接左中右
    finish(x,1);
    x->up();
}

void del(int x)//删掉排名第x的節點,,,,
{
    splay(rt,x-1);
    splay(rt->rc,2);//兩次提跟之後x就是root->rc->lc;
    rt->rc->lc=nil;//删掉
    rt->rc->up();
    rt->up();
}

void reverse(int x,int y)//旋轉區間[x,y]
{
    splay(rt,x-1);
    splay(rt->rc,y-x+2);//提出[x,y]
    rt->rc->lc->rev^=1;//放标記
}

void insert(int x,int y)//排名第x的後面增加一個節點,,值為y,,
{
    splay(rt,x);
    splay(rt->rc,1);
    rt->rc->lc=++pe;
    pe->clear(y);
    rt->rc->up();
    rt->up();
}

int getmin(int x,int y)//求[x,y]的最小值
{
    splay(rt,x-1);
    splay(rt->rc,y-x+2);
    return rt->rc->lc->mn;
}

void add(int x,int y,int z)//[x,y]内所有節點增加z,,
{
    splay(rt,x-1);
    splay(rt->rc,y-x+2);
    rt->rc->lc->add(z);
    rt->rc->up();
    rt->up();
}

void revolve(int x,int y,int z)//交換[x,x+z]和[x+z+1,y]
{//這裡一般有兩個算法,,1,提根出[x,y],在[x,y]中把x+z+1提根,,這樣出現[x,x+z];,,删掉[x,x+z],将y提根,,将[x,x+z]接到y的右邊
                     //2,把x+z+1提根,,左邊把x-1提根,,右邊把y+1提根,,這樣出現了[x,x+z]和[x+z+1,y],,交換之
    splay(rt,x-1);
    splay(rt->rc,y-x+2);
    node*&p=rt->rc->lc;//p就是[x,y]
    splay(p,z+1);
    node *q=p->lc;//q就是[x,x+z],用來儲存;
    p->lc=nil;
    p->up();
    splay(p,p->sz);//把y提根
    p->rc=q;
    p->up();
    rt->rc->up();
    rt->up();
}

int da[N],n,q;//data[]
void bld(node *&p,int l,int r)
{
    if(l>r)
        return;
    int mid=(l+r)/2;
    p=++pe;
    pe->clear(da[mid]);
    bld(p->lc,l,mid-1);
    bld(p->rc,mid+1,r);
    p->up();
}
int main()
{
    nil->sz=0;
    nil->mn=nil->w=oo;
    scanf("%d",&n);
    n+=2;
    int i;
    for(i=2;i<n;i++)
        scanf("%d",&da[i]);
    da[1]=da[n]=oo;
    bld(rt,1,n);

    for(scanf("%d",&q);q--;)
    {
        char s[10];
        int x,y,z;
        scanf("%s",s);
        if(strcmp(s,"ADD")==0)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x+1,y+1,z);
        }
        else if(strcmp(s,"REVERSE")==0)
        {
            scanf("%d%d",&x,&y);
            reverse(x+1,y+1);
        }
        else if(strcmp(s,"REVOLVE")==0)
        {
            scanf("%d%d%d",&x,&y,&z);
            int len=y-x+1;
            z=(z%len+len)%len;
            if(z)
                revolve(x+1,y+1,len-z);
        }
        else if(strcmp(s,"INSERT")==0)
        {
            scanf("%d%d",&x,&y);
            insert(x+1,y);
        }
        else if(strcmp(s,"DELETE")==0)
        {
            scanf("%d",&x);
            del(x+1);
        }
        else
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",getmin(x+1,y+1));
        }
    }
}