bzoj 3223 文艺平衡树

Splay 区间标记

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

Output

输出一行n个数字，表示原始序列经过m次变换后的结果

Sample Input

5 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

题解

假如我们要在Splay中修改区间的话，可以先查找siz值为l-1+1与r+1+1的两个节点，将一个旋转到根，另一个旋转到根的右儿子上，则要修改的区间就是根的右孩子的左子树，直接打标记即可

注意

1.标记是在每一次访问到一个新的节点是就要pushdown的

2.区分一个节点的排名和这个节点的值：这个节点的排名是它是当前数组中的第几个，用左儿子的size+1表示；这个节点的值是题目中输入的数字，在本题中是1~n

3.增加数字为1和n+2的两个哨兵节点，因为如果对区间1~x或 x~n操作，用到前后的节点就需要1和n+2。

4.注意build的写法，返回区间[l,r]的根节点的编号

#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);
}