hdu-1890-Robotic Sort-splay tree-區間翻轉

伸展樹對于區間的翻轉操作尤其的友善。

對于區間翻轉的時候，同樣使用lazy标記。

但是在splay操作的時候注意要先更新孩子，然後在判斷改左旋還是右旋。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 110000
#define mem(a,b) memset(a,b,sizeof(a))
struct splaytree
{
    int pre[maxn];
    int ch[maxn][2];
    int key[maxn];
    int rev[maxn];
    int size[maxn];
    int val[maxn];
    int sum[maxn];
    int root,tot;
    int n;
    void Treaval(int x)
    {
        if(x)
        {
            Treaval(ch[x][0]);
            printf("結點%2d:左兒子 %2d 右兒子 %2d 父結點 %2d size = %2d ,val = %2d , sum = %2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x],sum[x]);
            Treaval(ch[x][1]);
        }
    }
    void debug()
    {
        printf("%d\n",root);
        Treaval(root);
    }
    //debug專用
    struct list
    {
        int x;
        int st;
        friend bool operator < (const list &a,const list &b)
        {
            if(a.x!=b.x)return a.x<b.x;
            return a.st<b.st;
        }
    } node[maxn];
    void init()
    {
        root=tot=0;
        mem(pre,0);
        mem(ch,0);
        mem(rev,0);
        mem(size,0);
    }
    void newnode(int &x,int father,int k)
    {
        x=k;
        pre[x]=father;
        ch[x][0]=ch[x][1]=0;
        rev[x]=0;
        key[x]=k;
        size[x]=1;
    }
    void push_down(int x)
    {
        if(rev[x])
        {
            rev[ch[x][0]]^=1;
            rev[ch[x][1]]^=1;
            swap(ch[x][0],ch[x][1]);
            rev[x]=0;
        }
    }
    void push_up(int x)
    {
        size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
    }
    void rot(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);
        push_up(x);
    }
    void splay(int x,int goal)
    {
        push_down(x);
        while(pre[x]!=goal)
        {
            if(pre[pre[x]]==goal)
            {
                push_down(pre[x]);
                push_down(x);
                rot(x,ch[pre[x]][0]==x);
            }
            else
            {
                int y=pre[x];
                push_down(pre[y]);
                push_down(pre[x]);
                push_down(x);
                int kind=ch[pre[y]][0]==y;
                if(ch[y][kind]==x)
                {
                    rot(x,!kind);
                    rot(x,kind);
                }
                else
                {
                    rot(y,kind);
                    rot(x,kind);
                }
            }
        }
        push_up(x);
        if(goal==0)root=x;
    }
    int getmax(int x)
    {
        push_down(x);
        while(ch[x][1])
        {
            x=ch[x][1];
            push_down(x);
        }
        return x;
    }
    void erase(int x)
    {
        if(ch[root][0]==0)
        {
            root=ch[root][1];
            pre[root]=0;
        }
        else
        {
            int m=getmax(ch[root][0]);
            splay(m,root);
            ch[m][1]=ch[root][1];
            pre[ch[root][1]]=m;
            root=m;
            pre[root]=0;
            push_up(root);
        }
    }
    void buildtree(int &x,int l,int r,int father)
    {
        if(l>r)return ;
        int mid=(l+r)/2;
        //  cout<<x<<"--->";
        newnode(x,father,mid);
        // cout<<x<<endl;
        buildtree(ch[x][0],l,mid-1,x);
        buildtree(ch[x][1],mid+1,r,x);
        push_up(x);
    }
    void start()
    {
        sort(node+1,node+n+1);
        buildtree(root,1,n,0);
    }
} T;
int main()
{
    int n,i;
    while(scanf("%d",&n)!=EOF&&n)
    {
        T.init();
        T.n=n;
        for(i=1; i<=n; i++)
        {
            scanf("%d",&T.node[i].x);
            T.node[i].st=i;
        }
        T.start();
        //  T.debug();
        for(int i=1; i<n; i++)
        {
            //T.debug();
            T.splay(T.node[i].st,0);
            T.rev[T.ch[T.root][0]]^=1;
            printf("%d ",i+T.size[T.ch[T.root][0]]);
            T.erase(T.root);
        }
        printf("%d\n",n);
    }
    return 0;
}