题解 P3391 【【模板】文艺平衡树（Splay）】
远航之曲
2016-12-25 08:24:42
假如我们要在Splay中修改区间的话，可以先查找siz值为l与r+2的两个节点，将一个旋转到根，另一个旋转到根的左儿子上，则要修改的区间就是根的右孩子的左子树，直接打标记即可
注意
1.标记是在每一次访问到一个新的节点是就要pushdown的
2.区分一个节点的排名和这个节点的值：这个节点的排名是它是当前数组中的第几个，用左儿子的size+1表示；这个节点的值是题目中输入的数字，在本题中是1~n
3.增加数字为1和n+2的两个哨兵节点，因为如果对区间1~x或 x~n操作，用到前后的节点就需要1和n+2。
4.注意build的写法，返回区间[l,r]的根节点的编号
有缩进见[这里](http://www.yhzq-blog.cc/bzoj-3223-文艺平衡树/)
```cpp
#include <cstdio>
#define Maxn 100010
#define INF 0x3f3f3f3f
using namespace std;
int f[Maxn],ch[Maxn][2],siz[Maxn],mark[Maxn],key[Maxn],root,sz;
int data[Maxn];
int R() {int x=0,F=1;char C=getchar();while(C<'0'||C>'9'){if(C=='-')F=-F;C=getchar();}while(C>='0'&&C<='9')x=x*10-'0'+C,C=getchar();return x*F;}
inline int get(int x){return ch[f[x]][1]==x;}
inline void update(int x){siz[x]=siz[ch[x][1]]+siz[ch[x][0]]+1;}
inline void swap(int &x,int &y){int t=x;x=y;y=t;}
inline int pushdown(int x)
{
if (x && mark[x])
{
mark[ch[x][0]]^=1;
mark[ch[x][1]]^=1;
swap(ch[x][0],ch[x][1]);
mark[x]=0;
}
}
inline int rot(int x)
{
int k=get(x),fa=f[x],fafa=f[fa];
pushdown(fa);pushdown(x);
ch[fa][k]=ch[x][!k];f[ch[x][!k]]=fa;
ch[x][!k]=fa;f[fa]=x;
f[x]=fafa;
if (fafa) ch[fafa][ch[fafa][1]==fa]=x;
update(fa);update(x);
}
inline int splay(int x,int tar)
{
for (int fa;(fa=f[x])!=tar;rot(x))
if (f[fa]!=tar)
rot(get(fa)==get(x)?fa:x);
if (!tar) root=x;
}
inline int build(int fa,int l,int r)
{
if (l>r) return 0;
int mid=(l+r)>>1;
int now=++sz;
key[now]=data[mid],f[now]=fa,mark[now]=0;
ch[now][0]=build(now,l,mid-1);
ch[now][1]=build(now,mid+1,r);
update(now);
return now;
}
inline int findx(int k)
{
int now=root;
while(1)
{
pushdown(now);
if (k<=siz[ch[now][0]])
now=ch[now][0];
else
{
k-=siz[ch[now][0]]+1;
if (!k) return now;
now=ch[now][1];
}
}
}
inline void print(int now)
{
pushdown(now);
if (ch[now][0]) print(ch[now][0]);
if (key[now]!=-INF && key[now]!=INF)
printf("%d ",key[now]);
if (ch[now][1]) print(ch[now][1]);
}
main()
{
int n,m,x,y;
scanf("%d %d",&n,&m);
for (int i=1;i<=n;i++)
data[i+1]=i;
data[1]=-INF,data[n+2]=INF;
root=build(0,1,n+2);
for (int i=1;i<=m;i++)
{
x=R();
y=R();
int x1=findx(x),y1=findx(y+2);
splay(x1,0);
splay(y1,x1);
mark[ch[ch[root][1]][0]]^=1;
}
print(root);
}
```