牛客网暑期ACM多校训练营（第三场） C Shuffle Cards (SPLAY)

这个题就是每次把一段区间移动到区间的最前面，问你若干次操作后的序列

按照题解说，这个题就是一个平衡树的操作题，之前没有做过平衡树的题，但是移动区间的时候想到了连续的翻转操作可以使得区间移动，所以，然后找了一个splay区间翻转的板子过了这个题，赛后发现stl 中有十分简单的工具可以实现。
看来要学习的东西还有很多

#include<stdio.h>
#include<algorithm>
using namespace std;

struct node
{
    int sum,flag,siz;
    node *ch[2],*fa;
    void pushdown(node *nd)
    {
        if(flag)
        {
            swap(ch[0],ch[1]);
            if(ch[0]!=nd) ch[0]->flag^=1;
            if(ch[1]!=nd) ch[1]->flag^=1;
            flag=0;
        }
    }
    void update()
    {
        siz=ch[0]->siz+ch[1]->siz+1;
    }
}state[4000010],*tail=state,*root,*null;

int n,m;

void init()
{
    null=++tail;
    null->siz=0;
    null->ch[0]=null->ch[1]=null;
    null->sum=null->flag=0;
}

node* newnode(node *fa)
{
    node *nd=++tail;
    nd->fa=fa;
    nd->siz=1;
    nd->ch[1]=nd->ch[0]=null;
    nd->flag=0;
    return nd;
}

void rot ( node*& x, int d )
{
    node* y=x->fa;
    y->ch[!d]=x->ch[d];
    if(x->ch[d]!= null) x->ch[d]->fa=y ;
    x->fa=y->fa ;
    if(y->fa!=null)
        (y==y->fa->ch[0]) ? y->fa->ch[0]=x : y->fa->ch[1]=x;
    x->ch[d]=y;
    y->fa =x;
    x->update();
    y->update();
}

node *build(node *fa,int lf,int rg)
{
    if(lf>rg) return null;
    node *nd=newnode(fa);
    if(lf==rg)
    {
        nd->sum=lf;
        return nd;
    }
    int mid=(lf+rg)>>1;
    nd->sum=mid;
    nd->ch[0]=build(nd,lf,mid-1);
    nd->ch[1]=build(nd,mid+1,rg);
    nd->update();
    return nd;
}


void Splay(node *nd,node *tar)
{
    while(nd->fa!=tar)
    {
        node *ne=nd->fa;
        if(nd==ne->ch[0])
        {
            if(ne->fa!=tar&&ne==ne->fa->ch[0])
               rot(ne,1);
            rot(nd,1);
        }
        else
        {
            if(ne->fa!=tar&&ne==ne->fa->ch[1])
               rot(ne,0);
            rot(nd,0);
        }
    }
    if(tar==null) root=nd;
}

node *kth(node *nd,int K)
{
    nd->pushdown(null);
    if(nd->ch[0]->siz+1==K) return nd;
    if(nd->ch[0]->siz+1>K) return kth(nd->ch[0],K);
    else return kth(nd->ch[1],K-nd->ch[0]->siz-1);
}

void rev(int L,int R)
{
    node *x=kth(root,L);node *y=kth(root,R+2);
    Splay(x,null);
    Splay(y,root);
    y->ch[0]->flag^=1;
}

void GrandOrder(node *nd)
{
    if(nd==null) return ;
    nd->pushdown(null);
    GrandOrder(nd->ch[0]);
    if(nd->sum>=1&&nd->sum<=n)
    printf("%d ",nd->sum);
    GrandOrder(nd->ch[1]);
}

int main()
{
    init();
    int L,R;
    scanf("%d%d",&n,&m);
    root=build(null,0,n+1);
    while(m--)
    {
        scanf("%d%d",&L,&R);
        rev(1,L-1);
        rev(L,L+R-1);
        rev(1,L+R-1);
    }
    GrandOrder(root);
    return 0;
}