伸展树 解决区间问题
伸展树的基本操作就是伸展，也就是将指定节点旋转至树根（同时不改变排序二叉树的性质）。在这个操作的基础上，配合节点中保存额外的数据域，伸展树可以完成多种任务，包括各种区间问题。
伸展树的节点除了保存必要的指针信息和键值对之外，经常使用的额外的数据域包括size域、sum域、极值域等等。size域用于记录该节点所代表的子树的节点总数，可以用于解决区间kth数问题；sum域用于记录该节点所代表子树的所有节点的数值之和，可以解决区间和问题；极值域用于记录该子树所有节点的极值，可以解决RMQ问题。而且伸展树能够解决问题的范围非常广。不但可以解决静态区间问题，数值单点修改的区间问题，数值成段修改的区间问题，而且可以解决区间本身发生变动时问题。相比之下，ST算法只能解决静态RMQ，树状数组可以解决单点修改的区间和问题，线段树还能解决成段修改的区间问题，但是它们都不如伸展树覆盖的范围大，都不能解决最后一类问题。当然，伸展树适用范围虽然广，但是在解决特定问题时效率比较低，除非是特定的访问模式。
模板：
#include<bits/stdc++.h>
const int N=100000+5;
using namespace std;
int ch[N][3],siz[N],rev[N],val[N],fa[N],a[N];
int root,tail,n,m,x,y;
struct SPLAY{
void update(int pos){
siz[pos]=siz[ch[pos][0]]+siz[ch[pos][1]]+1;
}
void init(){
siz[0]=0;
root=build(0,a,1,n+2);
}
void pushdown(int nd){
if(rev[nd]){//翻转标记
ch[nd][0]^=ch[nd][1]^=ch[nd][0]^=ch[nd][1];
if(ch[nd][0]) rev[ch[nd][0]]^=1;
if(ch[nd][1]) rev[ch[nd][1]]^=1;
rev[nd]=0;
}
}
int build(int p,int *a,int l,int r){
if(l>r) return 0;
int mid=(l+r)>>1;
fa[mid]=p;
ch[mid][0]=build(mid,a,l,mid-1);
ch[mid][1]=build(mid,a,mid+1,r);
val[mid]=a[mid];
update(mid);
return mid;
}
void rotate(int nd,int pd){
int s=ch[nd][!pd];
int ss=ch[s][pd];
int p=fa[nd];
fa[nd]=s;
if(p) ch[p][nd==ch[p][1]]=s;
else root=s;
ch[s][pd]=nd;
ch[nd][!pd]=ss;
if(ss) fa[ss]=nd;
fa[s]=p;
update(nd);
update(s);
}
void splay(int nd,int top=0){
while(fa[nd]!=top){
int p=fa[nd];
int pp=fa[p];
int nl=nd==ch[p][0];
if(pp==top)
rotate(p,nl);
else{
int pl=p==ch[pp][0];
if(pl==nl){
rotate(pp,pl);
rotate(p,nl);
}
else{
rotate(p,nl);
rotate(pp,pl);
}
}
}
}
int find(int pos){
int nd=root;
while(1){
pushdown(nd);
if(pos<=siz[ch[nd][0]])
nd=ch[nd][0];
else if(pos>=siz[ch[nd][0]]+2){
pos-=siz[ch[nd][0]]+1;
nd=ch[nd][1];
}
else{
splay(nd);
return nd;
}
}
}
void erase(int pos){
int lnd=find(pos-1),rnd=find(pos+1);
splay(lnd);
splay(rnd,lnd);
ch[rnd][0]=0;
update(rnd);
update(lnd);
}
void reverse(int l,int r){
int lnd=find(l-1);
int rnd=find(r+1);
splay(lnd);
splay(rnd,lnd);
rev[ch[rnd][0]]^=1;//打上翻转标记，并且" ^ "保证了原本需要翻转的点现在不需要翻转了
pushdown(ch[rnd][0]);
splay(ch[rnd][0]);
}
}
worker;
int main(){
scanf("%d%d",&n,&m);
for(int i=2;i<=n+1;i++)
a[i]=i-1;
a[1]=0x7fffffff;
a[n+2]=0x7fffffff;
worker.init();
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
worker.reverse(x+1,y+1);
}
for(int i=2;i<=n+1;i++)
printf("%d ",worker.find(i)-1);
return 0;
}