luogu3391

P3391 【模板】文艺平衡树（Splay）

题目背景

这是一道经典的Splay模板题——文艺平衡树。

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n)  m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n 

Output

输出一行n个数字，表示原始序列经过m次变换后的结果 

Sample Input

5 3
1 3
1 3
1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

sol：闲的蛋疼打了一遍splay板子，还挂了一发。Ps：注意下传Rev标记

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=100005,inf=0x3f3f3f3f;
int n,m;
namespace Pht
{
    int Points=0,Root;
    int Child[N][2],Parent[N];
    int Size[N];
    int Quanzhi[N];
    bool Rev[N];

    inline void Init();
    inline int Check(int x);
    inline void PushUp(int x);
    inline void PushDown(int x);
    inline void Rotate(int x);
    inline void Splay(int At,int To);
    inline void Insert(int Val);
    inline int Ask_Kth(int Id);
    inline void Reverse(int l,int r);
    inline void Output(int Now);
    inline void Solve();
    
    inline void Init()
    {
        int i;
        Insert(-inf);
        for(i=1;i<=n;i++) Insert(i);
        Insert(inf);
    }
    inline int Check(int x)
    {
        return (Child[Parent[x]][0]==x)?0:1;
    }
    inline void PushUp(int x)
    {
        Size[x]=Size[Child[x][0]]+Size[Child[x][1]]+1;
    }
    inline void PushDown(int x)
    {
        if(!Rev[x]) return;
        swap(Child[x][0],Child[x][1]);
        Rev[x]=0;
        Rev[Child[x][0]]^=1;
        Rev[Child[x][1]]^=1;
    }
    inline void Rotate(int x)
    {
        int y,z,oo;
        y=Parent[x];
        z=Parent[y];
        oo=Check(x);
        Child[y][oo]=Child[x][oo^1]; Parent[Child[x][oo^1]]=y;
        Child[z][Check(y)]=x; Parent[x]=z;
        Child[x][oo^1]=y; Parent[y]=x;
        PushUp(x); PushUp(y);
    }
    inline void Splay(int At,int To)
    {
        while(Parent[At]!=To)
        {
            int Father=Parent[At];
            if(Parent[Father]==To)
            {
                Rotate(At);
            }
            else if(Check(At)==Check(Father))
            {
                Rotate(Father); Rotate(At);
            }
            else
            {
                Rotate(At); Rotate(At);
            }
        }
        if(To==0) Root=At;
    }
    inline void Insert(int Val)
    {
        int Now=Root,Par=0;
        while(Now)
        {
            Par=Now;
            Now=Child[Now][(Val>Quanzhi[Now])?1:0];
        }
        Now=++Points;
        if(Par)
        {
            Child[Par][(Val>Quanzhi[Par])?1:0]=Now;
        }
        Parent[Now]=Par;
        Child[Now][0]=Child[Now][1]=0;
        Quanzhi[Now]=Val;
        Size[Now]=1;
        Splay(Now,0);
    }
    inline int Ask_Kth(int Id)
    {
        int Now=Root;
        while(Now)
        {
            PushDown(Now);
            if(Size[Child[Now][0]]>=Id)
            {
                Now=Child[Now][0];
            }
            else if(Size[Child[Now][0]]+1==Id)
            {
                return Now;
            }
            else
            {
                Id=Id-Size[Child[Now][0]]-1;
                Now=Child[Now][1];
            }
        }
    }
    inline void Reverse(int l,int r)
    {
        int ll=Ask_Kth(l),rr=Ask_Kth(r+2);
        Splay(ll,0);
        Splay(rr,ll);
        int Pos=Child[rr][0];
        Rev[Pos]^=1;
    }
    inline void Output(int Now)
    {
        PushDown(Now);
        if(Child[Now][0]) Output(Child[Now][0]);
        if(Quanzhi[Now]>=1&&Quanzhi[Now]<=n) W(Quanzhi[Now]);
        if(Child[Now][1]) Output(Child[Now][1]);
    }
    inline void Solve()
    {
        Init();
        while(m--)
        {
            int l=read(),r=read();
            Reverse(l,r);
        }
        Output(Root);
    }
}
int main()
{
    R(n); R(m);
    Pht::Solve();
    return 0;
}
/*
input
5 3
1 3
1 3
1 4
output
4 3 2 1 5
*/