HDU 4286 Data Handler（12年天津 Splay tree）

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove

题目：有一串数字，两个指针，然后一些添加，删除，反转，以及移动操作，最后 输出序列

http://acm.hdu.edu.cn/showproblem.php?pid=4286

比赛的时候最后半小时才发现这题。

一看到题目就觉得是Splay tree。因为有一个反转操作，想都没想，就开始写了，不过最后只剩半小时，勉强只能过了样例。

其实这题的插入和删除都只是一个数字，Splay是很不沾优的，双向链表模拟一下更加方便，也比较好写。

不过对于我这种傻X就只能坚持撸Splay了。

各种悲剧，一开始是RE。因为Splay并不是严格的平衡树，极有可能退化，深度很大，在递归的时候，可能会出现堆栈溢出，一开始都是G++交的，没注意，苦逼调试很久。

之后便是一直TLE，不断得改变姿势，其实我的Splay效率还是可以的。哭瞎

最后也不知道是怎么就过了，加上外挂排在第一

#include<iostream>#include<cstring>#include<queue>#include<cstdio>#include<algorithm>#define N 1000005#define inf 1<<29#define MOD 100000007#define LL long long#define Key_value ch[ch[root][1]][0]#define _match(a,b) ((a)==(b))#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;int n,q,a[N],pl,pr;int size[N],pre[N],rev[N],sum[5],val[N];int ch[N][2],tot1,root,s[N],tot2;inline void NewNode(int &r,int k,int father){    if(tot2)        r=s[tot2--];    else        r=++tot1;    ch[r][0]=ch[r][1]=0;    pre[r]=father;    size[r]=1;    rev[r]=0;    val[r]=k;}inline void Push_Up(int x){    int l=ch[x][0],r=ch[x][1];    size[x]=size[l]+size[r]+1;}inline void Push_Down(int r){    if(rev[r]){        rev[ch[r][0]]^= 1;          rev[ch[r][1]]^= 1;          swap(ch[r][0],ch[r][1]);          rev[r]=0;      }}inline void Bulid(int &r,int L,int R,int father){    if(L>R)        return ;    int mid=(L+R)/2;    NewNode(r,a[mid],father);    Bulid(ch[r][0],L,mid-1,r);    Bulid(ch[r][1],mid+1,R,r);    Push_Up(r);}void Init(){    tot1=tot2=root=0;    ch[root][0]=ch[root][1]=pre[root]=rev[root]=size[root]=0;    NewNode(root,-100,0);    NewNode(ch[root][1],-1,root);    Push_Up(root);    Bulid(Key_value,1,n,ch[root][1]);    Push_Up(ch[root][1]);    Push_Up(root);}inline void Rotate(int x,int kind){    int y=pre[x];    Push_Down(y);    Push_Down(x);    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;    Push_Up(y);}inline void Splay(int r,int goal){    Push_Down(r);    while(pre[r]!=goal){        if(pre[pre[r]]==goal)            Rotate(r,ch[pre[r]][0]==r);        else{            int y=pre[r];            int kind=(ch[pre[y]][0]==y);            if(ch[y][kind]==r){                Rotate(r,!kind);                Rotate(r,kind);            }            else{                Rotate(y,kind);                Rotate(r,kind);            }        }    }    Push_Up(r);    if(goal==0) root=r;}inline void RotateTo(int k, int goal) {      int x=root;      Push_Down(x);      while(k!=size[ch[x][0]]+1){          if (k<=size[ch[x][0]]){              x=ch[x][0];          }else{              k-=(size[ch[x][0]]+1);              x=ch[x][1];          }          Push_Down(x);      }      Splay(x,goal);  }  void Print();inline void Reversal(int pos,int k){    RotateTo(pos,0);    RotateTo(pos+k+1,root);    rev[Key_value]^=1;}inline void Insert(int pos,int k,int num){    RotateTo(pos,0);    RotateTo(pos+1,root);    NewNode(Key_value,num,ch[root][1]);    Push_Up(ch[root][1]);    Push_Up(root);}inline void Delete(int pos,int k){    RotateTo(pos,0);    RotateTo(pos+k+1,root);    //删除节点，并更新    Key_value=0;    Push_Up(ch[root][1]);}int cnt,ans[N];//外挂忽略inline void scanf_(int &num){    char in;    bool neg=false;    while(((in=getchar()) > '9' || in<'0') && in!='-') ;    if(in=='-'){        neg=true;        while((in=getchar()) >'9' || in<'0');    }    num=in-'0';    while(in=getchar(),in>='0'&&in<='9')        num*=10,num+=in-'0';    if(neg)        num=0-num;}inline void printf_(int num){    bool flag=false;    if(num<0){        putchar('-');        num=-num;    }    int ans[10],top=0;    while(num!=0){        ans[top++]=num%10;        num/=10;    }    if(top==0)        putchar('0');    for(int i=top-1;i>=0;i--){        char ch=ans[i]+'0';        putchar(ch);    }}void InOrder(int r){    if(r==0)        return;    Push_Down(r);    InOrder(ch[r][0]);    if(cnt) putchar(' ');    printf_(val[r]);    cnt++;    InOrder(ch[r][1]);}void Print(){    //旋转后，便于递归输出，避免输出头尾冗余点    RotateTo(1,0);    RotateTo(n+2,root);    cnt=0;    InOrder(Key_value);    putchar('\n');}int main(){    int t;    scanf_(t);    while(t--){        scanf_(n);        for(int i=1;i<=n;i++)            scanf_(a[i]);        Init();        char str[20];        int k=1,pl,r1;        scanf_(pl);scanf_(pr);scanf_(q);        while(q--){            scanf("%s",str);            if(str[0]=='M'&&str[4]=='R'){                scanf("%s",str);                if(str[0]=='L') pl++;                else pr++;            }            else if(str[0]=='M'&&str[4]=='L'){                scanf("%s",str);                if(str[0]=='L') pl--;                else pr--;            }            else if(str[0]=='I'){                scanf("%s",str);                scanf_(a[1]);                if(str[0]=='L') {Insert(pl,k,a[1]);}                else {Insert(pr+1,k,a[1]);}                //插入的话，总字符数量增加1个，而且右边的指针后移                n++;pr++;            }            else if(str[0]=='D'){                scanf("%s",&str);                if(str[0]=='L') {Delete(pl,k);}                else {Delete(pr,k);}                //删除的话，总字符减1，右边的指针前移一个                n--;pr--;            }            else if(str[0]=='R')                Reversal(pl,pr-pl+1);        }        Print();    }    return 0;}