NKOJ 4340 （SCOI 2014）方伯伯的OJ （Splay+map+set）

发表于 |
字数统计: 1,473字 | 阅读时长 ≈ 8min

P4340【SCOI2014】方伯伯的Oj

问题描述

这里写图片描述

输入格式

输入的第1行包含2个用空格分隔的整数n和m，表示初始用户数和操作数。
此后有m行，每行是一个询问，询问格式如上所示。

输出格式

输出包含m行。每行包含一个整数，其中第i行的整数表示第i个操作的输出。

样例输入

10 10
1 2 11
3 13
2 5
3 7
2 8
2 10
2 11
3 14
2 18
4 9

样例输出

2
2
2
4
3
5
5
7
8
11

提示

对于 100% 的数据，1 ≤ n ≤ 10^8，1 ≤ m ≤ 10^5

输入保证对于所有的操作 1，2，3，x 必然已经出现在队列中，同时对于所有操作 1，1 ≤ y ≤ 2 × 10^8，并且

y 没有出现在队列中。

对于所有操作 4，保证 1 ≤ k ≤ n。

此题强制在线，观察发现$n$很大，那么显然此题应该根据$m$入手，考虑将Splay中的点维护一个区间，然后查询到了再拆开成3个点。

需要维护两个值，编号和排名，按照排名建立Splay，用map记录编号区间为$[a,b]$的点，还需要记录当前已经被拆过的点即查找过的位置，这样就可以通过编号找到在Splay中对应的位置，然后还需要开一个map记录表示一个点的点。

然后每种操作找到对应的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
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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#define N 1000005
using namespace std;
struct node
{
	int l,r;
	bool operator<(const node &b)const
	{
		if(l==b.l)return r<b.r;
		return l<b.l;
	}
};
set<int>A;
map<int,int>C;
map<node,int>B;
set<int>::iterator Ai;
map<node,int>::iterator Bi;
int n,m;
int rt,ls[N],rs[N],fa[N],id[N],lid[N],rid[N],v[N],si[N],tot;
void MT(int x)
{si[x]=si[ls[x]]+si[rs[x]]+v[x];}
void Zig(int x)
{
	int y=fa[x],z=fa[y];
	if(z)y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
	ls[y]=rs[x];fa[rs[x]]=y;
	rs[x]=y;fa[y]=x;
	MT(y);MT(x);
}
void Zag(int x)
{
	int y=fa[x],z=fa[y];
	if(z)y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
	rs[y]=ls[x];fa[ls[x]]=y;
	ls[x]=y;fa[y]=x;
	MT(y);MT(x);
}
void Splay(int x)
{
	int y,z;
	while(fa[x])
	{
		y=fa[x],z=fa[y];
		if(z)
		{
			if(y==ls[z])x==ls[y]?(Zig(y),Zig(x)):(Zag(x),Zig(x));
			else x==rs[y]?(Zag(y),Zag(x)):(Zig(x),Zag(x));
		}
		else x==ls[y]?Zig(x):Zag(x);
	}
	rt=x;
}
int Gmax(int p)
{
	while(rs[p])p=rs[p];
	return p;
}
int Gmin(int p)
{
	while(ls[p])p=ls[p];
	return p;
}
int Find(int x)
{
	node tmp;
	if(C.count(x))return C[x];
	Ai=A.lower_bound(x);
	tmp.r=*Ai-1;Ai--;
	tmp.l=*Ai+1;
	Bi=B.lower_bound(tmp);
	return Bi->second;
}
int Div(int p,int x)
{
	int l,r;node tmp;
	Splay(p);
	A.insert(x);
	l=ls[p];r=rs[p];
	fa[l]=fa[r]=ls[p]=rs[p]=0;
	if(lid[p]<x-1)
	{
		tot++;
		lid[tot]=lid[p];
		rid[tot]=x-1;
		v[tot]=x-lid[p];
		fa[l]=tot;ls[tot]=l;
		MT(tot);l=tot;
		tmp.l=lid[l];
		tmp.r=rid[l];
		B[tmp]=l;
	}
	else if(lid[p]==x-1)
	{
		tot++;
		id[tot]=lid[p];
		v[tot]=1;
		fa[l]=tot;
		ls[tot]=l;
		MT(tot);l=tot;
		C[lid[p]]=tot;
	}
	if(x+1<rid[p])
	{
		tot++;
		lid[tot]=x+1;
		rid[tot]=rid[p];
		v[tot]=rid[p]-x;
		fa[r]=tot;rs[tot]=r;
		MT(tot);r=tot;
		tmp.l=lid[r];
		tmp.r=rid[r];
		B[tmp]=r;
	}
	else if(x+1==rid[p])
	{
		tot++;
		id[tot]=x+1;
		v[tot]=1;
		fa[r]=tot;rs[tot]=r;
		MT(tot);r=tot;
		C[x+1]=tot;
	}
	fa[l]=fa[r]=++tot;
	ls[tot]=l;rs[tot]=r;
	id[tot]=x;v[tot]=1;
	C[x]=tot;MT(tot);
	return rt=tot;
}
void Del(int p)
{
	int l=ls[p],r=rs[p];
	fa[l]=fa[r]=ls[p]=rs[p]=0;
	if(!l)rt=r;
	else
	{
		l=Gmax(l);
		Splay(l);
		fa[r]=l;rs[l]=r;
		rt=l;MT(l);
	}
}
int Gkth(int k)
{
	int p=rt;
	while(p)
	{
		if(si[ls[p]]<k&&si[ls[p]]+v[p]>=k)return p;
		if(si[ls[p]]>=k)p=ls[p];
		else k-=si[ls[p]]+v[p],p=rs[p];
	}
	return p;
}
int main()
{
	int i,j,k,x,y,z,p,l,r,t;node tmp;
	scanf("%d%d",&n,&m);int ans=0;
	rt=++tot;lid[rt]=1;rid[rt]=n;v[rt]=si[rt]=n;
	A.insert(0);A.insert(n+1);
	tmp.l=1;tmp.r=n;B[tmp]=rt;
	while(m--)
	{
		scanf("%d",&k);
		if(k==1)
		{
			scanf("%d%d",&x,&y);
			x-=ans;y-=ans;p=Find(x);
			if(v[p]==1)
			{
				id[p]=y;C[y]=p;Splay(p);
				ans=si[ls[p]]+1;
				printf("%d\n",ans);
			}
			else
			{
				p=Div(p,x);id[p]=y;C[y]=p;
				ans=si[ls[p]]+1;
				printf("%d\n",ans);
			}
		}
		if(k==2)
		{
			scanf("%d",&x);
			x-=ans;p=Find(x);
			if(v[p]==1)
			{
				Splay(p);
				ans=si[ls[p]]+1;
				printf("%d\n",ans);
				Del(p);rs[p]=rt;fa[rt]=p;rt=p;
			}
			else
			{
				p=Div(p,x);
				ans=si[ls[p]]+1;
				printf("%d\n",ans);
				Del(p);rs[p]=rt;fa[rt]=p;rt=p;
			}
		}
		if(k==3)
		{
			scanf("%d",&x);
			x-=ans;p=Find(x);
			if(v[p]==1)
			{
				Splay(p);
				ans=si[ls[p]]+1;
				printf("%d\n",ans);
				Del(p);ls[p]=rt;fa[rt]=p;rt=p;
			}
			else
			{
				p=Div(p,x);
				ans=si[ls[p]]+1;
				printf("%d\n",ans);
				Del(p);ls[p]=rt;fa[rt]=p;rt=p;
			}
		}
		if(k==4)
		{
			scanf("%d",&x);
			x-=ans;p=Gkth(x);Splay(p);
			if(v[p]==1)ans=id[p],printf("%d\n",ans);
			else
			{
				t=x-si[ls[p]];
				x=lid[p]+t-1;
				p=Div(p,x);
				ans=id[p];
				printf("%d\n",ans);
			}
		}
	}
}