hdu 1890 Robotic Sort（Splay） - c++编程基础

题目大意：

机器人可以每次反转一个区间，要把当前最小的放在最前面。问他反转前，那个数在第几号位置。

思路：

可以知道Splay的左子树就是在他左边的数的个数，所以我们直接用他们的初始位置建树。

然后用num排序。这时可以用从小到大的顺序取出他们在数组中的位置。

把目标放在根节点。

然后找他的左子树的个数+i，然后删除根节点。

之前遇到一个思维上的问题，也是lcm提出来的。既然会反转，那么反转后的位置就变了呀。

比如

2 3 1

他们sort以后变成1 2 3.

此时找1，初始位置是3，反转之后变成1 3 2，然后删除节点1，变成 3 2

然后再找2，初始位置是1，但是此时1号位置是3 而不是2了。

后来想了一想，Splay的存放是放在一个静态数组，我们反转只是反转他的ch[x][0-1]。但是他自身存放的位置是不会变的。

所以只管去除数组中的第id号元素就可以了。

还有一个大问题！！！为什么这题用rotate会超时，用zigzag就不会啊。二者的区别是什么啊。也是看了爱酱的博客才发现的。。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define inf 0x3f3f3f3f #define maxn 122222 #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 rev[maxn]; struct node { int num,id; bool operator <(const node &cmp)const { if(num!=cmp.num)return num
      
       e)return; int mid=(s+e)>>1; New(x,f,mid); if(s
       
        mid)build(ch[x][1],mid+1,e,x); pushup(x); } inline void zig(int x){//左旋 int y=pre[x], z=pre[y]; ch[y][1]=ch[x][0]; pre[ch[x][0]]=y; ch[x][0]=y; pre[y]=x; pre[x]=z; if(z) ch[z][ch[z][1]==y]=x; pushup(y); } inline void zag(int x){//右旋 int y=pre[x], z=pre[y]; ch[y][0]=ch[x][1]; pre[ch[x][1]]=y; ch[x][1]=y; pre[y]=x; pre[x]=z; if(z) ch[z][ch[z][1]==y]=x; pushup(y); } inline void zigzig(int x){ int y=pre[x], z=pre[y], fz=pre[z]; ch[z][1]=ch[y][0]; pre[ch[y][0]]=z; ch[y][1]=ch[x][0]; pre[ch[x][0]]=y; pre[z]=y; ch[y][0]=z; pre[y]=x; ch[x][0]=y; pre[x]=fz; if(fz) ch[fz][ch[fz][1]==z]=x; pushup(z); pushup(y); } inline void zagzag(int x){ int y=pre[x], z=pre[y], fz=pre[z]; ch[z][0]=ch[y][1]; pre[ch[y][1]]=z; ch[y][0]=ch[x][1]; pre[ch[x][1]]=y; pre[z]=y; ch[y][1]=z; pre[y]=x; ch[x][1]=y; pre[x]=fz; if(fz) ch[fz][ch[fz][1]==z]=x; pushup(z); pushup(y); } inline void zigzag(int x){ int y=pre[x], z=pre[y], fz=pre[z]; ch[y][1]=ch[x][0]; pre[ch[x][0]]=y; ch[z][0]=ch[x][1]; pre[ch[x][1]]=z; pre[y]=pre[z]=x; ch[x][0]=y; ch[x][1]=z; pre[x]=fz; if(fz) ch[fz][ch[fz][1]==z]=x; pushup(z); pushup(y); } inline void zagzig(int x){ int y=pre[x], z=pre[y], fz=pre[z]; ch[y][0]=ch[x][1]; pre[ch[x][1]]=y; ch[z][1]=ch[x][0]; pre[ch[x][0]]=z; pre[y]=pre[z]=x; ch[x][1]=y; ch[x][0]=z; pre[x]=fz; if(fz) ch[fz][ch[fz][1]==z]=x; pushup(z); pushup(y); } void Splay(int x, int goal){ int y, z; pushdown(x); while(pre[x]!=goal){ if(pre[pre[x]]==goal){ y=pre[x]; pushdown(y); pushdown(x); if(ch[y][1]==x) zig(x); else zag(x); } else{ y=pre[x]; z=pre[y]; pushdown(z); pushdown(y); pushdown(x); if(ch[z][1]==y){ if(ch[y][1]==x) zigzig(x); else zagzig(x); } else{ if(ch[y][0]==x) zagzag(x); else zigzag(x); } } } pushup(x); if(pre[x]==0) root=x; } /* inline void Rotate(int x,int kind) { int y=pre[x]; pushdown(y); pushdown(x); ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; pre[x]=pre[y]; if(pre[x])ch[pre[y]][ch[pre[y]][1]==y]=x; ch[x][kind]=y; pre[y]=x; pushup(y); } 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; } */ void RorateTo(int k,int goal) { int r=root; pushdown(r); while(siz[ch[r][0]]!=k) { if(k