舒展树(splay tree)学习三：hdu1890 Robotic Sort

伸展树(splay tree)学习三：hdu1890 Robotic Sort
题目大意：给你n个数，每次将第i个位置到第i大的数所在位置之间的数进行翻转，输出的是第i大的数所在的位置

伸展树的节点编号的相对大小代表的是这个数在数组中的下标，并记录下第i大的数所在的节点编号是什么。

最后每次将第i大的数旋转到根，然后左子树的大小就是在数组中相对位置在这个数的左边的数的个数因为每次将第i大的数翻转到第i个位置时，这个数就不会用到了，

所以每次统计好后就直接把根节点给删了，这样的话答案就是 i+size[ch[root][0]] 。

#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<algorithm>  
#define N 100015  
#define inf 1<<29  
#define LL long long  
using namespace std;  
struct node{
       int num,rank;
       }a[N];
int pre[N],ch[N][2],root,tot;  //分别表示父结点，键值，左右孩子(0为左孩子，1为右孩子),根结点，结点数量  
int size[N];    
int rev[N];  
int n,q;  

inline void Newnode(int &r,int father,int k)
{  
    r=k;  
    pre[r]=father;  
    rev[r]=0;  
    size[r]=1;  
    ch[r][0]=ch[r][1]=0;  //左右孩子为空  
}
  
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 Push_Up(int r)//通过孩子结点更新父结点  
{  
    size[r]=size[ch[r][0]]+size[ch[r][1]]+1;  
} 

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;  
    pre[x]=pre[y];  
    if(pre[y])  
        ch[pre[y]][ch[pre[y]][1]==y]=x;  
    ch[x][kind]=y;  
    pre[y]=x;  
    Push_Up(y);
}

inline void Splay(int x,int goal) 
{
    Push_Down(x);
    while (pre[x]!=goal)
    {
        int y=pre[x],z=pre[y];
        Push_Down(z); Push_Down(y); Push_Down(x);
        if (pre[pre[x]]==goal)
            Rotate(x,ch[pre[x]][0] == x);
        else 
        {
             if (ch[z][0] == y) 
                 if (ch[y][0] == x) 
                     Rotate(y, 1), Rotate(x, 1);
                 else 
                     Rotate(x, 0), Rotate(x, 1);
             else 
                 if (ch[y][0] == x) 
                     Rotate(x, 1), Rotate(x, 0);
                 else 
                     Rotate(y, 0), Rotate(x, 0);
        }
    }
    Push_Up(x);
    if (goal == 0)  root=x;
}

inline void RotateTo(int k,int goal) //把第k位的数转到goal下边  
{  
    int r=root;  
    Push_Down(r);  
    while ((size[ch[r][0]]+1)!=k)
    {  
        if (k <= size[ch[r][0]])  
            r=ch[r][0];  
        else 
        {  
            k-=(size[ch[r][0]]+1);  
            r=ch[r][1];  
        }  
        Push_Down(r);  
    }  
    Splay(r,goal);  
}  

inline void Del_root()//删除根节点
{
    int t=root;
    if(ch[root][1]) 
    {
       root=ch[root][1];
       RotateTo(1,0);//把右子树中序遍历的第一个点旋转到根（因为这个点的左儿子肯定为空）
       ch[root][0]=ch[t][0];//将原先根节点的左子树接到当前根节点的左子树上
       if(ch[t][0]) pre[ch[t][0]]=root;
    }
    else 
       root=ch[root][0];
    pre[root]=0;
    Push_Up(root);
}

inline void Build(int &x,int l,int r,int fa)
{
    if (l > r)
        return;
    int mid=(l + r) >> 1;
    Newnode(x,fa,mid);
    Build(ch[x][0],l,mid-1,x);
    Build(ch[x][1],mid+1,r,x);
    Push_Up(x);
}

bool cmp(node a,node b)
{
    if (a.num!=b.num) return a.num<b.num;
    else return a.rank<b.rank;
}

inline void Init()
{
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&a[i].num);
        a[i].rank=i;
    }
    sort(a+1,a+n+1,cmp);
    ch[0][0]=ch[0][1]=pre[0]=size[0]=rev[0]=0;
    root=tot=0;
    Build(root,1,n,0);
}

int main()
{
    while (scanf("%d",&n)!=EOF && n)
    {
          Init();
          for (int i=1; i<n; i++)
          {
              Splay(a[i].rank,0);
              rev[ch[root][0]]^=1;
              printf("%d ",i+size[ch[root][0]]);
              Del_root();
          }
          printf("%d\n",n);
    }
    return 0;
}

舒展树(splay tree)学习三：hdu1890 Robotic Sort

相关推荐