【平衡树】文艺平衡树

平衡树

传送门：LOJ105

思路：

  • 用splay来维护序列；
  • 如果要提取区间$[l,r]$，就把$l-1$节点转到根，再把$r+1$转到根的右子节点，然后$r+1$的左子树即为所求区间；
  • 区间翻转打个标记即可；
  • 当一个点旋转时，需要把标记下传，如果有翻转标记，还要交换两棵子树位置。

注意：splay维护的是下标。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstdio>
using namespace std;
#define N 120000
int n,m,l,r,rt,son[N][2],rev[N],size[N],fa[N];
void pushdown(int x){
	int l=son[x][0],r=son[x][1];
	if (rev[x]){swap(son[x][0],son[x][1]); rev[l]^=1; rev[r]^=1; rev[x]=0;}
}
void rotate(int x,int w){
	int y=fa[x];
	size[y]=size[y]-size[x]+size[son[x][w]];
	size[x]=size[x]-size[son[x][w]]+size[y];
	son[y][w^1]=son[x][w]; if (son[x][w]) fa[son[x][w]]=y;
	fa[x]=fa[y]; if (fa[y]){if (y==son[fa[y]][0]) son[fa[y]][0]=x; else son[fa[y]][1]=x;}
	fa[y]=x; son[x][w]=y;
}
void splay(int x,int ff){
	while (fa[x]!=ff){
		int y=fa[x];
		if (fa[y]==ff){if (x==son[y][0]) rotate(x,1); else rotate(x,0);}
		else{
			if (x==son[y][0]){
				if (y==son[fa[y]][0]){rotate(y,1); rotate(x,1);}
				else{rotate(x,1); rotate(x,0);}
			}
			else{
				if (y==son[fa[y]][0]){rotate(x,0); rotate(x,1);}
				else{rotate(y,0); rotate(x,0);}
			}
		}
	}
	if (ff==0) rt=x;
}
int find(int cur,int rank){
	pushdown(cur);
	int l=son[cur][0],r=son[cur][1];
	if (size[l]+1==rank) return cur;
	if (size[l]>=rank) return find(l,rank); else return find(r,rank-size[l]-1);
}
void reverse(int l,int r){
	int x=find(rt,l-1),y=find(rt,r+1);
	splay(x,0); splay(y,x);
	rev[son[y][0]]^=1;
}
void build(int l,int r,int ff){
	if (l>r) return;
	int mid=(l+r)>>1;
	fa[mid]=ff; if (mid<ff) son[ff][0]=mid; else son[ff][1]=mid; size[mid]=1;
	if (l==r) return;
	build(l,mid-1,mid); build (mid+1,r,mid);
	size[mid]+=size[son[mid][0]]+size[son[mid][1]];
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,n+2,0); rt=(n+3)>>1;
	for (int i=1;i<=m;i++){scanf("%d%d",&l,&r); reverse(l+1,r+1);}
	for (int i=2;i<=n+1;i++) printf("%d ",find(rt,i)-1); puts("");
	
	return 0;
}