題意：
對于一個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;
}