题意：
对于一个1~n的序列，进行m次区间反转操作；
求m次反转之后的序列；
n，m<=100000；
题解：
splay躶题，写完维修数列之后感觉这样的题都好写了；
反转啥的打个标记下传就好，记得输出时再Pushdown标记就好了；
这篇题解就是说一下单旋和双旋的简单区别；
爷爷结点就是目标的情况不讨论了；
zig-zag实际上双旋与单旋的操作是一样的：
不同的是zig-zig操作：
根据某些神奇的势能分析(链接)，双旋大概比单旋快一些的；
(并且敢写单旋你不怕被各路神犇D吗)
但是经过我的几个小测试，其他函数一样，仅改变单旋双旋，时间并没有太多差别；
以下上为单旋下为双旋；
我就写了这么几道题，但是应该可以发现，无论单双都是可以AC的；
并且只有1588似乎有卡单旋的数据，所以单旋党的猖獗也不是没有道理嘛；
所以单旋双旋对于吾等蒟蒻是随便的的啦= =；
回归正题。。。发一下3223的代码吧；
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 110001
#define which(x) (ch[fa[x]][1]==x)
using namespace std;
int fa[N],ch[N][2],val[N],size[N],root,tot;
bool flag[N];
void Pushup(int x)
{
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void Pushdown(int x)
{
if(flag[x])
{
flag[ch[x][0]]^=1;
flag[ch[x][1]]^=1;
swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);
swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);
flag[x]=0;
}
}
void Rotate(int x)
{
int f=fa[x];
bool k=which(x);
ch[f][k]=ch[x][!k];
ch[x][!k]=f;
ch[fa[f]][which(f)]=x;
fa[x]=fa[f];
fa[ch[f][k]]=f;
fa[f]=x;
Pushup(f);
Pushup(x);
}
/* 单旋spaly
void Splay(int x,int g)
{
while(fa[x]!=g)
{
Rotate(x);
}
if(!g) root=x;
}
*/
void Splay(int x,int g)//双旋splay
{
while(fa[x]!=g)
{
int f=fa[x];
if(fa[f]==g)
{
Rotate(x);
break;
}
if(which(x)^which(f))
Rotate(x);
else
Rotate(f);
Rotate(x);
}
if(!g) root=x;
}
int Rank(int x,int k)
{
Pushdown(x);
if(k<=size[ch[x][0]])
return Rank(ch[x][0],k);
else if(k==size[ch[x][0]]+1)
return x;
else
return Rank(ch[x][1],k-size[ch[x][0]]-1);
}
int Build(int l,int r,int f)
{
if(l>r) return 0;
int mid=(l+r)>>1,x=++tot;
ch[x][0]=Build(l,mid-1,x);
ch[x][1]=Build(mid+1,r,x);
val[x]=mid;
fa[x]=f;
Pushup(x);
return x;
}
void Update(int l,int r)
{
int x,y,t;
x=Rank(root,l-1);
Splay(x,0);
y=Rank(root,r+1);
Splay(y,x);
t=ch[y][0];
swap(ch[t][0],ch[t][1]);
flag[t]^=1;
}
void Print(int x)
{
if(!x) return ;
Pushdown(x);
Print(ch[x][0]);
printf("%d ",val[x]);
Print(ch[x][1]);
}
int main()
{
int n,m,i,l,r;
scanf("%d%d",&n,&m);
root=Build(0,n+1,0);
for(i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
Update(l+1,r+1);
}
Splay(Rank(root,1),0);
Splay(Rank(root,n+2),root);
Print(ch[ch[root][1]][0]);
return 0;
}