hdu 4286 Data Handler (Splay)

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

而且还要C++扩栈。

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

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #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][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