题目链接

题目原文

小 T 有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用 11 到 nn 的正整数给每本书都编了号。

小 T 在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小 T 的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有 xx 本书，那么放回去时这本书上面就只可能有 x−1x-1 、 xx 或 x+1x+1 本书。

当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小 T 会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。

久而久之，小 T 的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：

  • 编号为 xx 的书在书柜的什么位置。
  • 从上到下第 ii 本书的编号是多少。

题解

一道splay的模板题，拿来熟悉splay的模板和理解splay的结构是很不错的。

Top 操作

首先将给的点旋转到根。

先判断其有没有左儿子，如果没有，那么这个点就已经是在top，不用进行任何操作。

再判断其有没有右儿子，如果没有，说明这个点在bottom，直接交换左右儿子即可。

如果既有左儿子又有右儿子，那么我们只需要将它的左儿子接到它的后继上，这样既满足了平衡树的规则，也满足了根节点没有左儿子，即该点是top的要求。

Bottom 操作

与Top操作同理。

Insert 操作

首先将给的点旋转到根。

如果t=1t=1，那么就直接将根节点与后继交换。
如果t=0t=0，相当于位置没有改变，直接忽略本次操作。
如果t=−1t=-1，那么就直接将根节点与前驱交换。

Ask 操作

就是求比根节点小的数的个数。

将根节点旋转到根，答案就是根节点左儿子的size。

Query 操作

就是找第k大。

总结与反思

在多次交换的时候一定要注意前后值是否发生改变，需不需要保留历史版本，太坑了。

代码

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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
/*************************************************
*           Copyright: lemonaaaaa                *
*           Author: lemonaaaaa                   *
*           Date: 2020-08-24                     *
*           Description: luogu P2596 splay tree  *
**************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
struct splay_tree
{
	int ch[maxn][2],fa[maxn],val[maxn],size[maxn],cnt[maxn],stack[maxn];
	int tot,root;
	splay_tree()
	{
		tot=root=0;
	}
	bool get(int x)
	{
		return ch[fa[x]][1]==x;
	}
	void update(int x)
	{
		if(!x) return;
		size[x]=cnt[x];
		if(ch[x][0]) size[x]+=size[ch[x][0]];
		if(ch[x][1]) size[x]+=size[ch[x][1]]; 
	}
	void clear(int x)
	{
		ch[x][0]=ch[x][1]=val[x]=fa[x]=size[x]=cnt[x]=0;
	}
	void rotate(int x)
	{
		int old=fa[x],oldfa=fa[old],w=get(x);
		ch[old][w]=ch[x][w^1];fa[ch[old][w]]=old;
		fa[old]=x;ch[x][w^1]=old;fa[x]=oldfa;
		if(oldfa) ch[oldfa][ch[oldfa][1]==old]=x;
		update(old);update(x);
	}
	void splay(int x,int tar)
	{
		for(int father;(father=fa[x])!=tar;rotate(x))
			if(fa[father]!=tar) rotate(get(x)==get(father)?father:x);
		if(!tar) root=x;
	}
	void insert(int x)
	{
		if(!root)
		{
			root=++tot;
			val[root]=x;
			cnt[root]=size[root]=1;
			return;
		}
		int now=root,father=0;
		while(true)
		{
			if(val[now]==x)
			{
				cnt[now]++;
				update(now);
				update(father);
				splay(now,0);
				break;
			}
			father=now;
			now=ch[now][x>val[now]];
			if(!now)
			{
				now=++tot;
				cnt[now]=size[now]=1;
				val[now]=x;
				fa[now]=father;
				ch[father][x>val[father]]=now;
				update(now);update(father);
				splay(now,0);
				break;
			}
		}
	}
	int find(int x)
	{
		int ans=0,now=root;
		while(true)
		{
			if(x<val[now]) now=ch[now][0];
			else
			{
				ans+=size[ch[now][0]];
				if(val[now]==x)
				{
					splay(now,0);
					return ans+1;
				}
				ans+=cnt[now];
				now=ch[now][1];
			}
		}
	}
	int findkth(int x)
	{
		int now=root;
		while(true)
		{
			if(ch[now][0]&&x<=size[ch[now][0]]) now=ch[now][0];
			else
			{
				int temp=size[ch[now][0]]+cnt[now];
				if(x<=temp) return val[now];
				x-=temp;now=ch[now][1];
			}
		}
	}
	int pre()
	{
		int now=ch[root][0];
		while(ch[now][1]) now=ch[now][1];
		return now;
	}
	int next()
	{
		int now=ch[root][1];
		while(ch[now][0]) now=ch[now][0];
		return now;
	}
	void del(int x)
	{
		find(x);
		if(cnt[root]>1)
		{
			cnt[root]--;
			update(root);
			return;
		}
		if(!ch[root][0]&&!ch[root][1])
		{
			clear(root);
			root=0;
			return;
		}
		if(!ch[root][0])
		{
			int oldroot=root;
			root=ch[root][1];
			fa[root]=0;
			clear(oldroot);
			return;
		}
		if(!ch[root][1])
		{
			int oldroot=root;
			root=ch[root][0];
			fa[root]=0;
			clear(oldroot);
		}
		int leftbig=pre(),oldroot=root;
		splay(leftbig,0);
		ch[root][1]=ch[oldroot][1];
		fa[ch[root][1]]=root;
		clear(oldroot);
		update(root);
		return;
	}
	void print(int x)
	{
		if(ch[x][0]) print(ch[x][0]);
		stack[++stack[0]]=val[x];
		if(ch[x][1]) print(ch[x][1]);
	}
};
int n,m,p[maxn],pos[maxn];
splay_tree tree;
char opt[10];
int main()
{
 	#ifdef lemon
//	freopen("P2596_1.in","r",stdin);
	freopen("2596.txt","r",stdin);
	#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		pos[p[i]]=i;
		tree.insert(i);
	}
//	for(int i=1;i<=n;i++) printf("##%d %d\n",i,tree.val[i]);
	for(int i=1,x,y;i<=m;i++)
	{
//		printf("$%d\n",i);
		scanf("%s%d",opt,&x);
		if(opt[0]=='T')
		{
			tree.splay(pos[x],0);
//			tree.find(pos[x]);
//			if(tree.root==pos[x]) printf("Yes\n");
			if(!tree.ch[tree.root][0]) continue;
			else if(!tree.ch[tree.root][1])
			{
//				printf("$$");
				tree.ch[tree.root][1]=tree.ch[tree.root][0];
				tree.ch[tree.root][0]=0;
			}
			else
			{
				int nxt=tree.next();
				tree.ch[nxt][0]=tree.ch[tree.root][0];
				tree.fa[tree.ch[nxt][0]]=nxt;
				tree.ch[tree.root][0]=0;
				tree.splay(nxt,0);
			}
		}
		else if(opt[0]=='B')
		{
			tree.splay(pos[x],0);
			if(!tree.ch[tree.root][1]) continue;
			else if(!tree.ch[tree.root][0])
			{
				tree.ch[tree.root][0]=tree.ch[tree.root][1];
				tree.ch[tree.root][1]=0;
			}
			else
			{
				int pre=tree.pre();
				tree.ch[pre][1]=tree.ch[tree.root][1];
				tree.fa[tree.ch[pre][1]]=pre;
				tree.ch[tree.root][1]=0;
				tree.splay(pre,0);
			}
		}
		else if(opt[0]=='I')
		{
			scanf("%d",&y);
			if(!y) continue;
			tree.splay(pos[x],0);
			if(y==1)
			{
				int nxt=tree.next();
				if(nxt==tree.root) continue;
//				swap(pos[p[nxt]],pos[x]);
				int pp=pos[x];
				pos[p[nxt]]=pos[x];pos[x]=nxt;
				swap(p[pp],p[nxt]);
			}
			else
			{
				int pre=tree.pre();
				if(pre==tree.root) continue;
//				swap(pos[p[pre]],pos[x]);
				int pp=pos[x];
				pos[p[pre]]=pos[x];pos[x]=pre;
				swap(p[pp],p[pre]);
			}
		}
		else if(opt[0]=='A')
		{
			tree.splay(pos[x],0);
			printf("%d\n",tree.size[tree.ch[tree.root][0]]);
		}
		else
		{
			printf("%d\n",p[tree.findkth(x)]);
		}
//		tree.stack[0]=0;
//		tree.print(tree.root);
//		for(int j=1;j<=tree.stack[0];j++) printf("%d ",p[tree.stack[j]]);
//		printf("\n");
	}
	return 0;
}