splay：伸展树，通过一系列的旋转维护平衡性。
注意，splay不一定是严格的平衡。故操作大部分均摊时间复杂度 \(O(logn)\)
分3种情况讨论旋转：
\(1.\) Zig \(or\) Zag
\(2.\) Zig-Zig \(or\) Zag-Zag （一字型，从左偏树到右偏树)
\(3.\) Zig-Zag \(or\) Zag-Zig （之字形转成一字型）
容易发现，旋转后树的中序遍历没有改变
splay的只因本操作
旋转
无需分开写左旋右旋
inline void rotate(int x) { int y=t[x].fa; int z=t[y].fa; int k=(rs(y)==x); t[z].son[rs(z)==y]=x; t[x].fa=z; t[y].son[k]=t[x].son[k^1]; t[t[x].son[k^1]].fa=y; t[x].son[k^1]=y; t[y].fa=x; pushup(y); pushup(x); }
查找
与二叉搜索树的查找相同，从根节点开始，如果要查询的值大于该点的值，递归右儿子，否则递归左二子。
如果找到了当前要查找的数，将此节点旋转到根节点上。
插入
如果出现过，节点的数量+1。
否则新建节点，找到合适位置插入。
插完以后旋转到根节点。
inline void insert(int v) { int u=root,p=0; while(u) { p=u; u=t[u].son[v>t[u].val]; } u=++cnt; if(p) { t[p].son[v>t[p].val]=u; } t[u].init(v,p); splay(u,0); }
删除
先找到此数的前驱，旋转到根节点。
再找后继，旋转到根节点的右儿子。
当前根节点的右儿子的左二子即为要删除的点。
提取区间
提取区间 \([x,y]\) ，将 \(x-1\) 旋转到根，将 \(y+1\) 旋转到根节点的右儿子。那么根节点的右儿子的左子树即为要提取的区间。
注意，当 \(x=0\) 时无 \(x-1\) 这个元素，当 \(y=n\) 时无 \(y+1\) 这个元素，解决方法是加入两个“哨兵”，插入在 \(0\) 和 \(n+1\) 的位置。
inline void qu(int &l,int &r) { l=getk(l); r=getk(r+2); splay(l,0); splay(r,l); }
区间翻转
区间翻转即为将区间内所有节点的左右子树进行交换。
首先提取区间（见上一个操作），随后交换根节点右儿子的左子树上每个节点的左右儿子。
inline void pushdown(int p) { if(t[p].lazy) { swap(ls(p),rs(p)); t[ls(p)].lazy^=1; t[rs(p)].lazy^=1; t[p].lazy=0; } }
P3391 【模板】文艺平衡树
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
namespace fastio
{
#define te template<typename T>
#define tem template<typename T,typename ...Args>
te inline static void read(T &x){x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}if(f==-1) x=-x;}
tem inline static void read(T& x,Args& ...args){read(x);read(args...);}
te inline static void write(char c,T x){T p=x;if(!p) putchar('0');if(p<0){putchar('-');p=-p;}int cnt[105],tot=0;while(p){cnt[++tot]=p%10;p/=10;}for(int i=tot;i>=1;i--){putchar(cnt[i]+'0');}putchar(c);}
tem inline static void write(const char c,T x,Args ...args){write(c,x);write(c,args...);}
}using namespace fastio;
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
const int N=1e5+10;
int n,m;
struct node
{
int son[2],fa,val;
int siz,lazy;
void init(int a,int b)
{
val=a;
fa=b;
siz=1;
}
}t[N];
int root,cnt;
inline void pushup(int p)
{
t[p].siz=t[ls(p)].siz+t[rs(p)].siz+1;
}
inline void pushdown(int p)
{
if(t[p].lazy)
{
swap(ls(p),rs(p));
t[ls(p)].lazy^=1;
t[rs(p)].lazy^=1;
t[p].lazy=0;
}
}
inline void rotate(int x)
{
int y=t[x].fa;
int z=t[y].fa;
int k=(rs(y)==x);
t[z].son[rs(z)==y]=x;
t[x].fa=z;
t[y].son[k]=t[x].son[k^1];
t[t[x].son[k^1]].fa=y;
t[x].son[k^1]=y;
t[y].fa=x;
pushup(y);
pushup(x);
}
void splay(int x,int k)
{
while(t[x].fa!=k)
{
int y=t[x].fa;
int z=t[y].fa;
if(z!=k)
{
if((rs(y)==x)^(rs(z)==y)) {rotate(x);}
else {rotate(y);}
}
rotate(x);
}
if(!k) root=x;
}
inline void insert(int v)
{
int u=root,p=0;
while(u)
{
p=u;
u=t[u].son[v>t[u].val];
}
u=++cnt;
if(p)
{
t[p].son[v>t[p].val]=u;
}
t[u].init(v,p);
splay(u,0);
}
int getk(int k)
{
int u=root;
while(1)
{
pushdown(u);
if(t[ls(u)].siz>=k)
{
u=ls(u);
}
else if(t[ls(u)].siz+1==k) return u;
else
{
k-=t[ls(u)].siz+1;
u=rs(u);
}
}
return -1;
}
inline void qu(int &l,int &r)
{
l=getk(l);
r=getk(r+2);
splay(l,0);
splay(r,l);
}
void print(int u)
{
pushdown(u);
if(ls(u))
{
print(ls(u));
}
if(t[u].val>=1&&t[u].val<=n)
{
write(' ',t[u].val);
}
if(rs(u))
{
print(rs(u));
}
}
int main()
{
read(n,m);
int l,r;
for(int i=0;i<=n+1;++i) {insert(i);}
while(m--)
{
read(l,r);
qu(l,r);
t[ls(r)].lazy^=1;
}
print(root);
return 0;
}