UVA 11922 Splay tree

UVA 11922

题意：

有n个数1~n

操作a,b表示取出第a~b个数，翻转后添加到数列的尾部

输入n,m

输入m条指令a,b

输出最终的序列

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define Key_Value ch[ch[root][1]][0]

const int maxn=;

int n,m;

int pre[maxn],rev[maxn],key[maxn],size[maxn],ch[maxn][],root,tot1;

void Update_Rev(int r){

    if(r==) return;

    swap(ch[r][],ch[r][]);

    rev[r]^=;

}

void Push_Down(int r){

    if(rev[r]){

        Update_Rev(ch[r][]);

        Update_Rev(ch[r][]);

        rev[r]=;

    }

}

void Push_Up(int r){

    size[r]=+size[ch[r][]]+size[ch[r][]];

}

void New_Node(int &r,int fa,int k){

    r=++tot1;

    pre[r]=fa;

    key[r]=k;

    rev[r]=ch[r][]=ch[r][]=;

    size[r]=;

}

void Build(int &x,int l,int r,int fa){

    if(l>r) return;

    int mid=(l+r)>>;

    New_Node(x,fa,mid);

    Build(ch[x][],l,mid-,x);

    Build(ch[x][],mid+,r,x);

    Push_Up(x);

}

void Init(){

    root=tot1=;

    pre[root]=rev[root]=key[root]=size[root]=ch[root][]=ch[root][]=;

    New_Node(root,,-);

    New_Node(ch[root][],root,-);

    Build(Key_Value,,n,ch[root][]);

    Push_Up(ch[root][]);

    Push_Up(root);

}

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]][]==y]=x;

    pre[x]=pre[y];

    ch[x][kind]=y;

    pre[y]=x;

    Push_Up(y);

}

void Splay(int r,int goal){

    while(pre[r]!=goal){

        if(pre[pre[r]]==goal)

            Rotate(r,ch[pre[r]][]==r);

        else{

            int y=pre[r];

            int kind=ch[pre[y]][]==y;

            if(ch[y][kind]==r){

                Rotate(r,!kind);

                Rotate(r,kind);

            }else{

                Rotate(y,kind);

                Rotate(r,kind);

            }

        }

    }

    Push_Up(r);

    if(goal==) root=r;

}

int Get_Kth(int r,int k){

    Push_Down(r);

    int t=size[ch[r][]];

    if(k==t+) return r;

    else if(k<=t) return Get_Kth(ch[r][],k);

    else return Get_Kth(ch[r][],k-t-);

}

void Solve(int a,int b){

    Splay(Get_Kth(root,a),);

    Splay(Get_Kth(root,b+),root);

    Update_Rev(Key_Value);

    Push_Up(ch[root][]);

    Push_Up(root);

    int temp=Key_Value;

    Key_Value=;

    Push_Up(ch[root][]);

    Push_Up(root);       //更改了Key_Value要pushup

    Splay(Get_Kth(root,size[root]-),);

    Splay(Get_Kth(root,size[root]),root);

    Key_Value=temp;

    pre[Key_Value]=ch[root][];

    Push_Up(ch[root][]);

    Push_Up(root);

}

int cnt;

void print(int r){

    if(r==) return;

    Push_Down(r);

    print(ch[r][]);

    if(cnt<n&&key[r]>){

        cnt++;

        printf("%d\n",key[r]);

    }

    print(ch[r][]);

}

int main()

{

    scanf("%d%d",&n,&m);

    Init();

    int x,y;

    while(m--){

        scanf("%d%d",&x,&y);

        Solve(x,y);

    }

    cnt=;

    print(root);

    return ;

}