Loj 2018 单旋

Posted on | Views:

LCT.

先考虑插入操作,经过观察容易发现,一个点被插入后,要么成为它前驱的右儿子,要么成为它后继的左儿子.

且这两个位置中恰有一个位置是空的,所以插入时在 set 中询问一下前驱后继即可.

考虑旋转操作,经过观察容易发现,如果把最小值转到根,就是先把它的右子树接在它的父亲上,再让它成为根的父亲.

旋转最大值也差不多,把它的左子树接在它的父亲上,再让它成为根的父亲.

如果接下来要将它删除,就不用从根向它连边.

而其他部分的形态是不变的,于是每次操作只会连/断 $O(1)$ 条边,可以用 LCT 来实现这些操作.

即,用一棵 LCT 维护这棵树的形态,另开数组记录每个节点在原树中的左右儿子以及父亲,并记录原树当前的根.

每次要询问一个点的深度时,就在 LCT 上询问它与根的距离即可.

可以先将所有权值离散化,然后将每个节点的权值当做它的标号.

时间复杂度 $O(m\log m)$ .

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
struct LCT
{
	struct node
	{
		int fa,ch[2],rev,siz;
		node(){fa=ch[0]=ch[1]=rev=0,siz=1;}
	}Tree[MAXN];
#define root Tree[x]
#define lson Tree[root.ch[0]]
#define rson Tree[root.ch[1]]
	void pushup(int x)
	{
		root.siz=lson.siz+rson.siz+1;
	}
	bool isroot(int x)
	{
		return Tree[root.fa].ch[0]!=x && Tree[root.fa].ch[1]!=x;
	}
	void rotate(int x)
	{
		int y=Tree[x].fa,z=Tree[y].fa;
		if(!isroot(y))
			Tree[z].ch[Tree[z].ch[1]==y]=x;
		Tree[x].fa=z;
		int k=Tree[y].ch[1]==x;
		Tree[y].ch[k]=Tree[x].ch[k^1];
		Tree[Tree[x].ch[k^1]].fa=y;
		Tree[x].ch[k^1]=y;
		Tree[y].fa=x;
		pushup(y);
	}
	int stk[MAXN],tp;
	void inverse(int x)
	{
		swap(root.ch[0],root.ch[1]);
		root.rev^=1;
	}
	void pushdown(int x)
	{
		if(root.rev)
		{
			if(root.ch[0])
				inverse(root.ch[0]);
			if(root.ch[1])
				inverse(root.ch[1]);
			root.rev=0;
		}
	}
	void Splay(int x)
	{
		stk[++tp]=x;
		for(int pos=x;!isroot(pos);pos=Tree[pos].fa)
			stk[++tp]=Tree[pos].fa;
		while(tp)
			pushdown(stk[tp--]);
		while(!isroot(x))
		{
			int y=Tree[x].fa,z=Tree[y].fa;
			if(!isroot(y))
				(Tree[y].ch[1]==x)^(Tree[z].ch[1]==y)?rotate(x):rotate(y);
			rotate(x);
		}
		pushup(x);
	}
	void Access(int x)
	{
		for(int y=0;x;y=x,x=Tree[x].fa)
		{
			Splay(x);
			Tree[x].ch[1]=y;
			pushup(x);
		}
	}
	void makeroot(int x)
	{
		Access(x);
		Splay(x);
		inverse(x);
	}
	void split(int x,int y)
	{
		makeroot(x);
		Access(y);
		Splay(y);
	}
	void link(int x,int y)
	{
		if(!x || !y)
			return;
		makeroot(x);
		Tree[x].fa=y;
	}
	void cut(int x,int y)
	{
		if(!x || !y)
			return;
		split(x,y);
		Tree[x].fa=Tree[y].ch[0]=0;
		pushup(y);
	}
	int query(int x,int y)
	{
		split(x,y);
		return Tree[y].siz;
	}
	LCT(){tp=Tree[0].siz=0;}
	
}T;
int n=0,m,tp[MAXN],val[MAXN],key[MAXN];
int rt,fa[MAXN],ch[MAXN][2];
set<int> s;
set<int>::iterator it;
int main()
{
	m=read();
	for(int i=1;i<=m;++i)
	{
		tp[i]=read();
		if(tp[i]==1)
			val[++n]=key[i]=read();
	}
	sort(val+1,val+1+n);
	for(int i=1;i<=m;++i)
		if(tp[i]==1)
			key[i]=lower_bound(val+1,val+1+n,key[i])-val;
	for(int i=1;i<=m;++i)
	{
		int ans;
		if(tp[i]==1)
		{
			int x=key[i];
			if(s.empty())
				rt=x,ans=1;
			else
			{
				it=s.lower_bound(x);
				int r=(it==s.end())?0:*it;
				int l=(it==s.begin())?0:*(--it);
				if(l && !ch[l][1])
				{
					ch[l][1]=x;
					fa[x]=l;
					T.link(l,x);
				}
				else
				{
					ch[r][0]=x;
					fa[x]=r;
					T.link(r,x);
				}
				ans=T.query(x,rt);
			}
			s.insert(x);	
		}
		else if(tp[i]==2 || tp[i]==4)
		{
			int x=*s.begin();
			ans=T.query(x,rt);
			int y=ch[x][1];
			T.cut(x,y);
			T.cut(x,fa[x]);
			T.link(fa[x],y);
			fa[y]=fa[x],ch[fa[x]][0]=y,fa[x]=0;
			if(x==rt)
				rt=y;
			if(tp[i]==2)
			{
				if(x!=rt)
				{
					fa[rt]=x;
					ch[x][1]=rt;
					T.link(x,rt);
					rt=x;
				}
			}
			else
				s.erase(x);
		}
		else
		{
			int x=*s.rbegin();
			ans=T.query(x,rt);
			int y=ch[x][0];
			T.cut(x,y);
			T.cut(x,fa[x]);
			T.link(fa[x],y);
			fa[y]=fa[x],ch[fa[x]][1]=y,fa[x]=0;
			if(x==rt)
				rt=y;
			if(tp[i]==3)
			{
				if(x!=rt)
				{
					fa[rt]=x;
					ch[x][0]=rt;
					T.link(x,rt);
					rt=x;
				}
			}
			else
				s.erase(x);
		}
		printf("%d\n",ans);
	}
	return 0;
}