hdu 4286 Data Handler (Splay)

splay 的基本操作，但是我真是服了。  N 是 50W   还有  50W个操作，所以需要把splay的数组开到100W.

而且还要C++扩栈。

需要注意的是  插入的时候  rpos 要 +1    删除的时候要  -1

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
#define maxn 1000005
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define keyTree (ch[ch[root][1]][0])

using namespace std;
typedef long long LL;
int S[maxn],que[maxn],ch[maxn][2],pre[maxn],siz[maxn];
int root,top1,top2;

int val[maxn],a[maxn],rev[maxn];
int lpos,rpos;
bool first;

inline void New(int &x,int PRE,int v)
{
    if(top2)x=S[--top2];
    else x=++top1;

    ch[x][0]=ch[x][1]=0;
    siz[x]=1;
    pre[x]=PRE;
    /*special*/
    val[x]=v;
    rev[x]=0;
}
inline void pushup(int x)/*special*/
{
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
inline void pushdown(int x)/*special*/
{
    if(rev[x])
    {
        rev[ch[x][0]]^=rev[x];
        rev[ch[x][1]]^=rev[x];
        swap(ch[x][0],ch[x][1]);
        rev[x]=0;
    }
}
inline void build(int &x,int s,int e,int f)
{
    if(s>e)return;
    int mid=(s+e)>>1;

    New(x,f,a[mid]);

    if(s<mid)build(ch[x][0],s,mid-1,x);
    if(e>mid)build(ch[x][1],mid+1,e,x);
    pushup(x);
}

inline void Rotate(int x,int kind)
{
    int y=pre[x];
    pushdown(x);
    pushdown(y);
    ch[y][!kind]=ch[x][kind];
    pre[ch[x][kind]]=y;
    if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    ch[x][kind]=y;
    pre[y]=x;
    pushup(y);
}

inline void Splay(int x,int goal)
{
    pushdown(x);
    while(pre[x]!=goal)
    {
        if(pre[pre[x]]==goal)
        Rotate(x,ch[pre[x]][0]==x);
        else
        {
            int y=pre[x];
            int kind=ch[pre[y]][0]==y;
            if(ch[y][kind]==x){
                Rotate(x,!kind);
                Rotate(x,kind);
            }
            else {
                Rotate(y,kind);
                Rotate(x,kind);
            }
        }
    }
    pushup(x);
    if(goal==0)root=x;
}
inline void RotateTo(int k,int goal)
{
    int r=root;
    pushdown(r);
    while(siz[ch[r][0]]!=k)
    {
        if(k<siz[ch[r][0]])
        {
            r=ch[r][0];
        }
        else
        {
            k-=siz[ch[r][0]]+1;
            r=ch[r][1];
        }
        pushdown(r);
    }
    Splay(r,goal);
}
inline void init(int n)
{
    root=top1=top2=0;
    ch[0][0]=ch[0][1]=siz[0]=pre[0]=rev[0]=val[0]=0;

    New(root,0,-1);
    New(ch[root][1],root,-1);

    siz[root]=2;

    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    build(keyTree,0,n-1,ch[root][1]);

    pushup(ch[root][1]);
    pushup(root);
}
inline void print(int x)
{
    if(x)
    {
        pushdown(x);
        print(ch[x][0]);
        if(first){printf("%d",val[x]);first=false;}
        else {printf(" %d",val[x]);}
        print(ch[x][1]);
    }
}
int main()
{
    int n,m;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        first=true;
        scanf("%d",&n);
        init(n);
        scanf("%d",&lpos);scanf("%d",&rpos);scanf("%d",&m);
        while(m--)
        {
            char str[100];
            char op[10];
            int v;
            scanf("%s",str);
            if(str[0]==‘M‘ && str[4]==‘L‘)
            {
                scanf("%s",op);
                if(op[0]==‘R‘)
                rpos--;
                else lpos--;
            }
            else if(str[0]==‘M‘&& str[4]==‘R‘)
            {
                scanf("%s",op);
                if(op[0]==‘R‘)
                rpos++;
                else lpos++;
            }
            else if(str[0]==‘I‘)
            {
                scanf("%s",op);
                scanf("%d",&v);
                if(op[0]==‘R‘)
                {
                    RotateTo(rpos,0);
                    RotateTo(rpos+1,root);
                    New(keyTree,ch[root][1],v);
                    pushup(ch[root][1]);
                    pushup(root);
                    rpos++;
                }
                else
                {
                    RotateTo(lpos-1,0);
                    RotateTo(lpos,root);
                    New(keyTree,ch[root][1],v);
                    pushup(ch[root][1]);
                    pushup(root);
                    rpos++;
                }
            }
            else if(str[0]==‘D‘)
            {
                scanf("%s",op);
                if(op[0]==‘R‘)
                {
                    RotateTo(rpos-1,0);
                    RotateTo(rpos+1,root);
                    S[top2++]=keyTree;
                    keyTree=0;
                    pushup(ch[root][1]);
                    pushup(root);
                    rpos--;
                }
                else
                {
                    RotateTo(lpos-1,0);
                    RotateTo(lpos+1,root);
                    S[top2++]=keyTree;
                    keyTree=0;
                    pushup(ch[root][1]);
                    pushup(root);
                    rpos--;
                }
            }
            else if(str[0]==‘R‘)
            {
                RotateTo(lpos-1,0);
                RotateTo(rpos+1,root);

                rev[keyTree]^=1;
            }

        }
        Splay(1,0);
        Splay(2,root);
        print(keyTree);
        puts("");
    }
    return 0;
}

hdu 4286 Data Handler (Splay),布布扣,bubuko.com

hdu 4286 Data Handler (Splay)

原文：http://blog.csdn.net/u010709592/article/details/21556459