萌新求助Splay

RT，照着 tiger0132 的日报学的 Splay

//2021/8/5

#include <cstdio>

#include <algorithm>

using namespace std;

const int ma=100005;

struct Splay
{
    int son[3];

    int val,fa;

    int size,cnt;
};

Splay node[ma];

int tag[ma];

int root,chd;

int n,m;

inline bool chk(int p)
{
    return node[node[p].fa].son[1]==p;
}

inline void PushUp(int p)
{
    node[p].size=node[node[p].son[0]].size+node[node[p].son[1]].size+node[p].cnt;
}

inline void Rotate(int p)
{
    int y=node[p].fa,k=chk(p),w=node[p].son[k^1];

    node[y].son[k]=w,node[w].fa=y;

    node[node[y].fa].son[chk(y)]=p,node[p].fa=node[y].fa;

    node[p].son[k^1]=y,node[y].fa=p;

    PushUp(y);

    PushUp(p); 
}

inline void splay(int p,int goal=0)
{
    while(node[p].fa!=goal)
    {
        int y=node[p].fa,z=node[y].fa;

        if(z!=goal)
        {
            if(chk(p)!=chk(y))
            {
                Rotate(y);
            }

            else
            {
                Rotate(p);
            }
        }

        Rotate(p);
    }

    if(goal==0)
    {
        root=p;
    }
}

inline void Find(int k)
{
    if(root==0)
    {
        return;
    }

    int cur=root;

    while(node[cur].son[k>node[cur].val]!=0 && k!=node[cur].val)
    {
        cur=node[cur].son[k>node[cur].val];
    }

    splay(cur);
}

inline void Insert(int k)
{
    int cur=root,p=0;

    while(cur!=0 && node[cur].val!=k)
    {
        p=cur;

        cur=node[cur].son[k>node[cur].val];
    }

    if(cur!=0)
    {
        node[cur].cnt++;
    }

    else
    {
        cur=++chd;

        if(p!=0)
        {
            node[p].son[k>node[cur].val]=cur;
        }

        node[cur].son[0]=node[cur].son[1]=0;

        node[cur].fa=p,node[cur].val=k;

        node[cur].size=node[cur].cnt=1;
    }

    splay(cur);
}

inline int kth(int rk)
{
    int cur=root;

    while(true)
    {
        if(node[cur].son[0]!=0 && node[node[cur].son[0]].size>=rk)
        {
            cur=node[cur].son[0];
        }

        else if(rk>node[node[cur].son[0]].size+node[cur].cnt)
        {
            rk=rk-node[node[cur].son[0]].size-node[cur].cnt;

            cur=node[cur].son[1];
        }

        else
        {
            splay(cur);

            return cur;
        }
    }
}

inline int GetPre(int val)
{
    Find(val);

    if(val>node[root].val)
    {
        return root;
    }

    int cur=node[root].son[0];

    while(node[cur].son[1]!=0)
    {
        cur=node[cur].son[1];
    }

    splay(cur);

    return cur;
}

inline int GetSucc(int val)
{
    Find(val);

    if(val<node[root].val)
    {
        return root;
    }

    int cur=node[root].son[1];

    while(node[cur].son[0]!=0)
    {
        cur=node[cur].son[0];
    }

    splay(cur);

    return cur;
}

inline void Remove(int val)
{
    int pre=GetPre(val),succ=GetSucc(val);

    splay(pre);

    splay(succ,pre);

    int del=node[succ].son[0];

    if(node[del].cnt>1)
    {
        node[del].cnt--;

        splay(del);
    }

    else
    {
        node[succ].son[0]=0;
    }

    PushUp(succ);

    PushUp(pre); 
}

inline void PushDown(int p)
{
    if(tag[p]!=0)
    {
        swap(node[p].son[0],node[p].son[1]);

        tag[node[p].son[0]]^=1;

        tag[node[p].son[1]]^=1;

        tag[p]=0; 
    }
}

inline void rev(int l,int r)
{
    int x=kth(l),y=kth(r+2);

    splay(x);

    splay(y,x);

    tag[node[y].son[0]]^=1; 
}

//中序遍历输出 
inline void print(int k)
{
    PushDown(k);

    if(node[k].son[0]!=0)
    {
        print(node[k].son[0]);
    }

    if(node[k].val!=0 && node[k].val<=n)
    {
        printf("%d ",node[k].val);
    }

    if(node[k].son[1]!=0)
    {
        print(node[k].son[1]);
    }
}

int main(void)
{
    //freopen("in.txt","r",stdin); 

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

    for(register int i=0;i<=n+1;i++)
    {
        Insert(i);
    }

    while(m--)
    {
        int l,r;

        scanf("%d%d",&l,&r);

        rev(l,r);
    }

    print(root);

    return 0;
}