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
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=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=,inf=0x3f3f3f3f;
int n,m;
namespace Pht
{
int Points=,Root;
int Child[N][],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=;i<=n;i++) Insert(i);
Insert(inf);
}
inline int Check(int x)
{
return (Child[Parent[x]][]==x)?:;
}
inline void PushUp(int x)
{
Size[x]=Size[Child[x][]]+Size[Child[x][]]+;
}
inline void PushDown(int x)
{
if(!Rev[x]) return;
swap(Child[x][],Child[x][]);
Rev[x]=;
Rev[Child[x][]]^=;
Rev[Child[x][]]^=;
}
inline void Rotate(int x)
{
int y,z,oo;
y=Parent[x];
z=Parent[y];
oo=Check(x);
Child[y][oo]=Child[x][oo^]; Parent[Child[x][oo^]]=y;
Child[z][Check(y)]=x; Parent[x]=z;
Child[x][oo^]=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==) Root=At;
}
inline void Insert(int Val)
{
int Now=Root,Par=;
while(Now)
{
Par=Now;
Now=Child[Now][(Val>Quanzhi[Now])?:];
}
Now=++Points;
if(Par)
{
Child[Par][(Val>Quanzhi[Par])?:]=Now;
}
Parent[Now]=Par;
Child[Now][]=Child[Now][]=;
Quanzhi[Now]=Val;
Size[Now]=;
Splay(Now,);
}
inline int Ask_Kth(int Id)
{
int Now=Root;
while(Now)
{
PushDown(Now);
if(Size[Child[Now][]]>=Id)
{
Now=Child[Now][];
}
else if(Size[Child[Now][]]+==Id)
{
return Now;
}
else
{
Id=Id-Size[Child[Now][]]-;
Now=Child[Now][];
}
}
}
inline void Reverse(int l,int r)
{
int ll=Ask_Kth(l),rr=Ask_Kth(r+);
Splay(ll,);
Splay(rr,ll);
int Pos=Child[rr][];
Rev[Pos]^=;
}
inline void Output(int Now)
{
PushDown(Now);
if(Child[Now][]) Output(Child[Now][]);
if(Quanzhi[Now]>=&&Quanzhi[Now]<=n) W(Quanzhi[Now]);
if(Child[Now][]) Output(Child[Now][]);
}
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 ;
}
/*
input
5 3
1 3
1 3
1 4
output
4 3 2 1 5
*/