Note - Splay

Posted on Edited on

  • Splay是一种平衡树，能做到单次查询均摊复杂度为 O(log⁡n)O(\log n) 。

  • 容易忘的东西： lazytaglazytag 未清零。。。 son(x,0)son(x,0) 忘记套 sz()sz() 。。。 splay()splay() 忘记更新根节点。。。 maintainmaintain 忘记。。。倒是 splaysplay 每次都记得写。。。

复杂度分析

主要内容

要点：splay操作

设当前节点为 xx 。

  • 如果当前节点是根节点，不进行操作。

  • 如果 fa(x)fa(x) 是根节点，那么 rotate(x)rotate(x) 。

  • 如果 fa(fa(x)),fa(x),xfa(fa(x)),fa(x), x 三点一线，那么 rotate(fa(x))rotate(fa(x)) ，再 rotate(x)rotate(x) 。

  • 如果 fa(fa(x)),fa(x),xfa(fa(x)),fa(x), x 三点不共线，那么连续进行两次 rotate(x)rotate(x) 。

  • 每次操作完一定要记得splay(多Splay使树更加平衡，不会被极端数据卡掉）。

复杂度是真的看不懂。。。

一些细节的处理

变量：

  • son[x][0/1]son[x][0/1] 表示 xx 的左/右儿子。

  • val[x]val[x] 表示 xx 节点的值。

  • cnt[x]cnt[x] 表示 xx 节点的值出现次数。

  • rtrt 表示根节点的编号。

  • fa[x]fa[x] 表示 xx 节点的父节点的编号。

  • sz[x]sz[x] 表示以 xx 节点为根的子树的 cntcnt 之和。

  • idxidx 表示用过的节点数量。

基本函数：

  • maintain(x)maintain(x) 更新 xx 节点的 szsz 。
1
2
3
inline void maintain(int x){
	sz[x]=sz[son[x][0]]+sz[son[x][1]]+cnt[x];
}
  • get(x)get(x) 返回非根节点 xx 是左儿子还是右儿子。
1
2
3
inline bool get(int x){
	return x==son[fa[x]][1];
}
  • clear(x)clear(x) 清空 xx 节点的信息。
1
2
3
inline void clear(int x){
	son[x][0]=son[x][1]=fa[x]=val[x]=cnt[x]=sz[x]=0;
}
  • rotate(x)rotate(x) 将 xx 节点向上旋转。
1
2
3
4
5
6
7
8
9
10
inline void rotate(int x){
	int y=fa[x],z=fa[y],p=get(x);
	son[y][p]=son[x][p^1];
	if (son[x][p^1]) fa[son[x][p^1]]=y;
	son[x][p^1]=y;
	fa[x]=z;
	fa[y]=x;
	if (z) son[z][y==son[z][1]]=x;
	maintain(y),maintain(x);
}
  • splay(x)splay(x) 将 xx 节点旋转到根节点。
1
2
3
4
5
6
7
inline void splay(int x){
	if (!x) return;
	for (int f=fa[x];f=fa[x],f;rotate(x)){
		if (f!=rt) rotate(get(f)==get(x)?f:x);
	}
	rt=x;
}
  • getrank(x)getrank(x) 查询 xx 的排名。
1
2
3
4
5
6
7
8
9
10
11
12
inline int getrank(int x){
	int cur=rt,res=0;
	while (cur){
		if (val[cur]<x) res+=sz[son[cur][0]]+cnt[cur],cur=son[cur][1];
		else if (val[cur]==x){
			res+=sz[son[cur][0]]+1,splay(cur);return res;
		}
		else cur=son[cur][0];
	}
	splay(fa[cur]);
	return res+1;
}
  • rtpre()rtpre() 找到根节点的前驱，并将其转到根节点。
1
2
3
4
5
6
inline int rtpre(){
	int cur=son[rt][0];
	while (son[cur][1]) cur=son[cur][1];
	splay(cur);
	return cur;
}

  • ins(x)ins(x) 插入值 xx 。

  • 如果是空树，直接插入。

  • 按查找树的顺序找值 xx ，若找到，就 cnt+1cnt+1 ；若找不到，在此处插入 xx 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void ins(int x){
	if (!rt){
		rt=++idx,val[idx]=x,cnt[idx]=1,sz[idx]=1;
		return;
	}
	int cur=rt,f=0;
	while (cur){
		if (val[cur]==x){
			++cnt[cur],++sz[cur];
			maintain(f);splay(cur);return;
		}
		f=cur,cur=son[cur][x>val[cur]];
		if (!cur){
			cnt[++idx]=1,sz[idx]=1,val[idx]=x,fa[idx]=f,son[f][x>val[f]]=idx;
			maintain(f);splay(idx);return;
		}
	}
}
  • findk(x)findk(x) 找到第 kk 大的数。
1
2
3
4
5
6
7
8
9
inline int findk(int x){
	int cur=rt;
	while (cur&&(x>sz[son[cur][0]]+cnt[cur]||x<=sz[son[cur][0]])){
		if (sz[son[cur][0]]>=x) cur=son[cur][0];
		else x-=sz[son[cur][0]]+cnt[cur],cur=son[cur][1];
	}
	splay(cur);
	return cur;
}

  • del(x)del(x) 删除值 xx 。

  • 先将值 xx 转到根节点；如果没有两个儿子，直接删。

  • 有两个儿子，找到前驱，让前驱当树根，则此节点一定没有左子树，并且是前驱的右子树。删掉，儿子上来即可。

1
2
3
4
5
6
7
8
9
10
11
inline void del(int x){
	int cur=findk(getrank(x));splay(cur);
	if (cnt[cur]>1) return --cnt[cur],--sz[cur],void();
	if (!son[cur][0]||!son[cur][1]){
		fa[son[cur][1]+son[cur][0]]=0,rt=son[cur][0]+son[cur][1],clear(cur);
		return;
	}
	int i=rtpre();
	--sz[fa[son[i][1]=son[cur][1]]=i];
	clear(cur);
}

  • pre(x)/nxt(x)pre(x)/nxt(x) 找值 xx 的前驱/后继。

  • 查询排名，在找到对应排名的数即可。

1
2
3
4
5
6
inline int pre(int x){
	return val[findk(getrank(x)-1)];
}
inline int nxt(int x){
	return val[findk(getrank(x+1))];
}

P3369 【模板】普通平衡树 ACAC 代码：

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
#include<bits/stdc++.h>//Splay
#define gc getchar
#define pc putchar
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
inline int read(){
	int x=0;bool p=1;char ch=gc();
	while (!isdigit(ch)) ch=='-'?p=0:0,ch=gc();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return p?x:-x;
}
inline void put(int x){
	if (x) put(x/10),pc('0'+x%10);
}
inline void print(int x){
	if (x>0) put(x);
	else if (x<0) pc('-'),put(-x);
	else pc('0');
	pc('\n');
}
const int N=1e5+3;
int son[N][2],fa[N],val[N],cnt[N],idx,rt,sz[N];
inline void maintain(int x){
	sz[x]=sz[son[x][0]]+sz[son[x][1]]+cnt[x];
}
inline bool get(int x){
	return x==son[fa[x]][1];
}
inline void clear(int x){
	son[x][0]=son[x][1]=fa[x]=val[x]=cnt[x]=sz[x]=0;
}
inline void rotate(int x){
	int y=fa[x],z=fa[y],p=get(x);
	son[y][p]=son[x][p^1];
	if (son[x][p^1]) fa[son[x][p^1]]=y;
	son[x][p^1]=y;
	fa[x]=z;
	fa[y]=x;
	if (z) son[z][y==son[z][1]]=x;
	maintain(y),maintain(x);
}
inline void splay(int x){
	if (!x) return;
	for (int f=fa[x];f=fa[x],f;rotate(x)){
		if (f!=rt) rotate(get(f)==get(x)?f:x);
	}
	rt=x;
}
inline int getrank(int x){
	int cur=rt,res=0;
	while (cur){
		if (val[cur]<x) res+=sz[son[cur][0]]+cnt[cur],cur=son[cur][1];
		else if (val[cur]==x){
			res+=sz[son[cur][0]]+1,splay(cur);return res;
		}
		else cur=son[cur][0];
	}
	splay(fa[cur]);
	return res+1;
}
inline int rtpre(){
	int cur=son[rt][0];
	while (son[cur][1]) cur=son[cur][1];
	splay(cur);
	return cur;
}
inline void ins(int x){
	if (!rt){
		rt=++idx,val[idx]=x,cnt[idx]=1,sz[idx]=1;
		return;
	}
	int cur=rt,f=0;
	while (cur){
		if (val[cur]==x){
			++cnt[cur],++sz[cur];
			maintain(f);splay(cur);return;
		}
		f=cur,cur=son[cur][x>val[cur]];
		if (!cur){
			cnt[++idx]=1,sz[idx]=1,val[idx]=x,fa[idx]=f,son[f][x>val[f]]=idx;
			maintain(f);splay(idx);return;
		}
	}
}
inline int findk(int x){
	int cur=rt;
	while (cur&&(x>sz[son[cur][0]]+cnt[cur]||x<=sz[son[cur][0]])){
		if (sz[son[cur][0]]>=x) cur=son[cur][0];
		else x-=sz[son[cur][0]]+cnt[cur],cur=son[cur][1];
	}
	splay(cur);
	return cur;
}
inline void del(int x){
	int cur=findk(getrank(x));splay(cur);
	if (cnt[cur]>1) return --cnt[cur],--sz[cur],void();
	if (!son[cur][0]||!son[cur][1]){
		fa[son[cur][1]+son[cur][0]]=0,rt=son[cur][0]+son[cur][1],clear(cur);
		return;
	}
	int i=rtpre();
	--sz[fa[son[i][1]=son[cur][1]]=i];
	clear(cur);
}
inline int pre(int x){
	return val[findk(getrank(x)-1)];
}
inline int nxt(int x){
	return val[findk(getrank(x+1))];
}
int n;
signed main(){
	n=read();
	F(i,1,n){
		int op=read(),x=read();
		if (op==1) ins(x);else
		if (op==2) del(x);else
		if (op==3) print(getrank(x));else
		if (op==4) print(val[findk(x)]);else
		if (op==5) print(pre(x));else
		if (op==6) print(nxt(x));
	}
	return 0;
}

进阶运用

P3391 【模板】文艺平衡树

首先，我们建一棵中序遍历为 1...n1...n 的二叉树。

由于无论如何旋转树的中序遍历都不会变，我们在操作区间 [l,r][l,r] 的时候可以将 l−1l-1 这个点转到根节点， r+1r+1 这个点转到根节点的右儿子。这个时候，不难发现，以根节点的右儿子的左儿子为根的子树上的所有节点就是我们需要操作的区间中的数。

如何进行区间翻转呢？由于我们规定数列是二叉树的中序遍历，我们只需将子树中的所有左儿子和右儿子互换（相当于原先遍历为左中右，现在为右中左）就可以做到翻转区间了。

一个个翻转肯定要超时，故可以开一个 lazytaglazytag （类似线段树）。

ACAC 代码：

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
#include<bits/stdc++.h>//Splay
#define gc getchar
#define pc putchar
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
inline int read(){
	int x=0;char ch=gc();
	while (!isdigit(ch)) ch=gc();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return x;
}
inline void put(int x){
	if (x) put(x/10),pc('0'+x%10);
}
template<typename TT> inline void swap(TT& x,int& y){
	TT z=x;x=y;y=z;
}
const int N=1e5;
struct Splay{
	int fa,son[2],tag,sz;
	#define fa(x) G[x].fa
	#define son(x,y) G[x].son[y]
	#define tag(x) G[x].tag
	#define sz(x) G[x].sz
} G[N+11];
int rt;
inline void maintain(int x){ sz(x)=sz(son(x,0))+sz(son(x,1))+1; }
inline bool get(int x){ return x==son(fa(x),1); }
inline void pushdown(int x){//下传标记，几乎和线段树一样 
	if (x&&tag(x)){
		swap(son(x,0),son(x,1));
		tag(son(x,0))^=1,tag(son(x,1))^=1;
		tag(x)=0;
	}
}
inline void rotate(int x){
	int y=fa(x),z=fa(y),p=get(x);
	pushdown(x),pushdown(y);//注意：旋转时同样要下传 
	son(y,p)=son(x,p^1);
	if (son(y,p)) fa(son(y,p))=y;
	son(x,p^1)=y,fa(y)=x;
	fa(x)=z;if (z) son(z,y==son(z,1))=x;
	maintain(y),maintain(x);
}
inline void splay(int x,int y){//将 x 转到 y 的 儿子节点 
	if (!x) return;
	for (int f=fa(x);(f=fa(x))!=y;rotate(x)){
		if (fa(f)!=y) rotate(get(x)==get(f)?f:x);
	}
	if (!y) rt=x;
}
inline int findk(int x){
	int cur=rt;
	while (cur&&sz(son(cur,tag(cur)))+1!=x){//注意：这里易错！要考虑有翻转标记的情况！ 
		pushdown(cur);
		if (sz(son(cur,0))>=x) cur=son(cur,0);
		else x-=sz(son(cur,0))+1,cur=son(cur,1);
	}
	splay(cur,0);return cur;
}
inline void rev(int x,int y){
	x=findk(x),y=findk(y);//找到中序遍历的为第 x/y 个的节点 
	splay(x,0),splay(y,rt);
	tag(son(y,0))^=1;
}
int build(int l,int r,int f){//递归建树 
	if (l>r) return 0;
	int mid=l+r>>1;
	fa(mid)=f;
	son(mid,0)=build(l,mid-1,mid);
	son(mid,1)=build(mid+1,r,mid);
	maintain(mid);
	return mid;
}
int n,m,p[N+11],idx;
void Dfs(int cur){//输出：别忘了pushdown 
	pushdown(cur);
	if (son(cur,0)) Dfs(son(cur,0));
	p[++idx]=cur;
	if (son(cur,1)) Dfs(son(cur,1));
}
signed main(){
	n=read(),m=read();
	build(1,n+2,0),rt=n+3>>1;
	F(i,1,m){
		int l=read(),r=read();
		rev(l,r+2);
	}
	Dfs(rt);
	F(i,2,n+1) put(p[i]-1),pc(' ');
	return 0;
}

P3165 [CQOI2014]排序机械臂

和文艺平衡树几乎相同的操作。注意：在 splaysplay 一个点之前必须从根开始向下全部 pushdownpushdown 一遍。代码为：

1
2
3
4
5
6
7
8
9
while (cur!=rt){
	st[++top]=cur;
	cur=fa(cur);
}
while (cur!=x){
	pushdown(cur);
	cur=son(cur,son(cur,1)==st[top--]);
}
splay(x);

调试拉满的 CodeCode ：

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
#include<bits/stdc++.h>
#define gc getchar
#define pc putchar
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
inline int read(){
	int x=0;char ch=gc();
	while (!isdigit(ch)) ch=gc();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return x;
}
inline void put(int x){
	if (x) put(x/10),pc('0'+x%10);
}
const int N=1e5+11;
struct Splay{
	int son[2],tag,sz,fa;
	#define son(x,y) G[x].son[y]
	#define tag(x) G[x].tag
	#define sz(x) G[x].sz
	#define fa(x) G[x].fa
} G[N];
int n,rt;
struct node{
	int val,tag;
} A[N];
inline bool cmpval(node a,node b){
	return a.val==b.val?a.tag<b.tag:a.val<b.val;
}
inline bool cmptag(node a,node b){
	return a.tag<b.tag;
}
inline void OUT(){
	F(i,1,n+2) printf("%d :: fa=%d son0=%d son1=%d sz=%d tag=%d rt=%d\n",i,fa(i),son(i,0),son(i,1),sz(i),tag(i),rt);
}
inline void maintain(int x){
	sz(x)=sz(son(x,0))+sz(son(x,1))+1;
}
inline bool get(int x){
	return x==son(fa(x),1);
}
inline void clear0(){
	son(0,0)=son(0,1)=tag(0)=sz(0)=fa(0)=0;
}
int build(int le,int ri,int f){
	if (le>ri) return 0;
	int mid=le+ri>>1,k=A[mid].val;
	fa(k)=f;
	son(k,0)=build(le,mid-1,k);
	son(k,1)=build(mid+1,ri,k);
	maintain(k);return k;
}
inline void swap(int& a,int& b){
	int c=a;a=b;b=c;
}
inline void pushdown(int x){
	if (x&&tag(x)){
		swap(son(x,0),son(x,1));
		tag(son(x,0))^=1,tag(son(x,1))^=1;
		clear0();
		tag(x)=0;
	}
}
inline void rotate(int x){
	int y=fa(x),z=fa(y);bool p=get(x);
	pushdown(y),pushdown(x);
	son(y,p)=son(x,p^1);if (son(y,p)) fa(son(y,p))=y;
	son(x,p^1)=y,fa(y)=x;
	if (z) son(z,son(z,1)==y)=x;fa(x)=z;
	maintain(y),maintain(x);
	clear0();
}
inline void splay(int x,int y){
	if (!x) return;
	for (int f;(f=fa(x))!=y;rotate(x)){
		if (fa(f)!=y) rotate(get(f)==get(x)?f:x);
	}
	if (!y) rt=x;
	clear0();
}
inline int findk(int x){
	int cur=rt;//OUT();
	while (cur&&sz(son(cur,tag(cur)))+1!=x){
		pushdown(cur);//printf("FINDK:: cur=%d x=%d sz=%d\n",cur,x,sz(son(cur,0)));
		if (sz(son(cur,0))>=x) cur=son(cur,0);
		else x-=sz(son(cur,0))+1,cur=son(cur,1);
	}//printf("FINDK::CUR= %d\n",cur);
	return splay(cur,0),cur;
}
int st[N];
inline int ans(int x){
	int top=0,cur=x;
	while (cur!=rt){
		st[++top]=cur;
		cur=fa(cur);
	}//puts("INANS::::::");OUT();
	while (cur&&cur!=x){
		pushdown(cur);
		cur=son(cur,son(cur,1)==st[top--]);
	}//printf("ANS::%d\n",x);
	splay(x,0);return sz(son(rt,0))+1;
}
inline void rev(int x,int y){
	//printf("\nREV:: %d <-> %d \n",x,y);
	if (x+2>=y) return;
	x=findk(x),y=findk(y);
	splay(x,0),splay(y,x);
	tag(son(y,0))^=1;
}
signed main(){
	n=read();
	F(i,2,n+1) A[i].val=read(),A[i].tag=i;
	A[1].val=1,A[1].tag=1,A[n+2].val=n+2,A[n+2].tag=n+2;
	std::sort(A+2,A+2+n,cmpval);
	F(i,2,n+1) A[i].val=i;
	std::sort(A+2,A+2+n,cmptag);
	build(1,n+2,0);rt=A[n+3>>1].val;
	F(i,1,n){
		int x=ans(i+1);
		put(x-1),pc(' ');
		rev(i,x+1);
	}
	return 0;
}

P3380 【模板】二逼平衡树（树套树）

线段树每个点开个 SplaySplay 即可。

操作 22 要二分，得 log3log^3 。

细节贼坑爹。。。不要注释掉 returnreturn 啊！

Code:Code:

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
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define pc putchar
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
inline int read(){
	int x=0;char ch=gc();
	while (!isdigit(ch)) ch=gc();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return x;
}
inline void put(int x){
	if (x) put(x/10),pc('0'+x%10);
}
inline void print(int x){
	if (x>0) put(x);
	else if (x<0) pc('-'),put(-x);
	else pc('0');
	pc('\n');
}
const int N=5e4+11;
struct Splay{
	int val,fa,son[2],sz,cnt;
} none;
vector<Splay> G[N<<2];int rt[N<<2],A[N],idx[N<<2],n,m;
#define val(y,x) G[y][x].val
#define fa(y,x) G[y][x].fa
#define sz(y,x) G[y][x].sz
#define son(z,x,y) G[z][x].son[y]
#define cnt(y,x) G[y][x].cnt
const int INF=2147483647;
inline void OUT(int pos){
	F(i,0,(int)(G[pos].size()-1)){
		printf("%d :: %d :: val=%d fa=%d sz=%d son=%d,%d cnt=%d rt=%d idx=%d\n"
		,pos,i,val(pos,i),fa(pos,i),sz(pos,i),son(pos,i,0),son(pos,i,1),cnt(pos,i),rt[pos],idx[pos]);
	}
}
inline void maintain(int pos,int x){
	if (!x) return;
	sz(pos,x)=sz(pos,son(pos,x,0))+sz(pos,son(pos,x,1))+cnt(pos,x);
}
inline bool get(int pos,int x){
	return x==son(pos,fa(pos,x),1);
}
inline void clear(int pos,int x){
	val(pos,x)=fa(pos,x)=sz(pos,x)=son(pos,x,0)=son(pos,x,1)=cnt(pos,x)=0;
}
inline void rotate(int pos,int x){
	int y=fa(pos,x),z=fa(pos,y);bool p=get(pos,x);
	son(pos,y,p)=son(pos,x,p^1);if (son(pos,y,p)) fa(pos,son(pos,y,p))=y;
	son(pos,x,p^1)=y,fa(pos,y)=x;
	if (z) son(pos,z,y==son(pos,z,1))=x;fa(pos,x)=z;
	maintain(pos,y),maintain(pos,x);
}
inline void splay(int pos,int x){
	if (!x) return;
	for (int f;(f=fa(pos,x));rotate(pos,x)){
		if (fa(pos,f)) rotate(pos,get(pos,x)==get(pos,f)?f:x);
	}
	rt[pos]=x;
}
inline int findk(int pos,int x){
	if (x<=0) return -INF;
	if (x>sz(pos,rt[pos])) return INF;
	int cur=rt[pos];
	while (sz(pos,son(pos,cur,0))>=x||sz(pos,son(pos,cur,0))+cnt(pos,cur)<x){
		if (sz(pos,son(pos,cur,0))>=x) cur=son(pos,cur,0);
		else x-=sz(pos,son(pos,cur,0))+cnt(pos,cur),cur=son(pos,cur,1);
	}
	return splay(pos,cur),cur;
}
inline int getrank(int pos,int x){
	int cur=rt[pos],res=0;
	while (cur){
		if (val(pos,cur)<x) res+=sz(pos,son(pos,cur,0))+cnt(pos,cur),cur=son(pos,cur,1);
		else if (val(pos,cur)==x) return res+=sz(pos,son(pos,cur,0)),splay(pos,cur),res;
		else cur=son(pos,cur,0);
	}
	return splay(pos,fa(pos,cur)),res;
}
inline void ins(int pos,int x){
	if (!rt[pos]){
		G[pos].push_back(none);++idx[pos];
		cnt(pos,idx[pos])=1,val(pos,idx[pos])=x,fa(pos,idx[pos])=0,sz(pos,idx[pos])=1,rt[pos]=idx[pos];
		return;
	}
	int cur=rt[pos],f=0;
	while (cur){
		if (val(pos,cur)==x){
			++cnt(pos,cur),++sz(pos,cur),maintain(pos,f),splay(pos,cur);
			return;
		}
		f=cur,cur=son(pos,cur,val(pos,cur)<x);
	}
	G[pos].push_back(none);++idx[pos];
	cnt(pos,idx[pos])=1,val(pos,idx[pos])=x,fa(pos,idx[pos])=f,sz(pos,idx[pos])=1;
	if (f) son(pos,f,val(pos,f)<x)=idx[pos];
	maintain(pos,f),splay(pos,idx[pos]);
}
inline void rtpre(int pos){
	int cur=son(pos,rt[pos],0);
	while (son(pos,cur,1)) cur=son(pos,cur,1);
	splay(pos,cur);
}
inline void del(int pos,int x){
	x=findk(pos,getrank(pos,x)+1);
	//printf("INDEL::::::delete %d rt=%d\n",x,rt[pos]);
	if (cnt(pos,x)>1) return --cnt(pos,x),--sz(pos,x),void();
	if (!son(pos,x,0)||!son(pos,x,1)){//printf("son0=%d son1=%d\n",son(pos,x,0),son(pos,x,1));
		fa(pos,son(pos,x,0)+son(pos,x,1))=0,rt[pos]=son(pos,x,0)+son(pos,x,1),clear(pos,x);
		//printf("RT = %d\n",rt[pos]);
		return;
	}
	rtpre(pos);
	//if (pos==4640) puts("INDEL::"),OUT(pos);
	fa(pos,son(pos,x,1))=rt[pos],son(pos,rt[pos],1)=son(pos,x,1),clear(pos,x),maintain(pos,rt[pos]);
}
void Build(int k,int l,int r){
	G[k].push_back(none);
	F(i,l,r) ins(k,A[i]);
	//puts("OUT:::");
	//OUT(k);
	if (l==r) return;
	int mid=l+r>>1;
	Build(k<<1,l,mid),Build(k<<1|1,mid+1,r);
}
int Queryrank(int k,int l,int r,int le,int ri,int v){
	if (le<=l&&ri>=r) return getrank(k,v);
	int mid=l+r>>1,res=0;
	if (mid>=le) res+=Queryrank(k<<1,l,mid,le,ri,v);
	if (mid<ri) res+=Queryrank(k<<1|1,mid+1,r,le,ri,v);
	return res;
}
inline void tomax(int& x,int y){
	if (y>x) x=y;
}
inline void tomin(int& x,int y){
	if (y<x) x=y;
}
int Querypre(int k,int l,int r,int le,int ri,int v){
	if (le<=l&&ri>=r){
		int d=findk(k,getrank(k,v));
		return d==-INF?d:val(k,d);
	}
	int mid=l+r>>1,res=-INF;
	if (mid>=le) tomax(res,Querypre(k<<1,l,mid,le,ri,v));
	if (mid<ri) tomax(res,Querypre(k<<1|1,mid+1,r,le,ri,v));
	return res;
}
int Querynxt(int k,int l,int r,int le,int ri,int v){
	if (le<=l&&ri>=r){
		int d=findk(k,getrank(k,v+1)+1);
		return d==INF?d:val(k,d);
	}
	int mid=l+r>>1,res=INF;
	if (mid>=le) tomin(res,Querynxt(k<<1,l,mid,le,ri,v));
	if (mid<ri) tomin(res,Querynxt(k<<1|1,mid+1,r,le,ri,v));
	return res;
}
int Queryk(int le,int ri,int v){
	int a=0,b=1e8;
	while (a<b){
		int mid=a+b+1>>1;
		int d=Queryrank(1,1,n,le,ri,mid);
		if (d<v) a=mid;
		else b=mid-1;
	}
	return b;
}
void Modify(int k,int l,int r,int p,int v){
	//printf("M:::: %d %d %d %d %d\n",k,l,r,p,v);//
	//
	//OUT(k);//
	//if (r-l==12) puts("BEFORE"),OUT(k);//
	del(k,A[p]);
	//
	//OUT(k);//
	//if (r-l==12) puts("NOW"),OUT(k);
	ins(k,v);
	//
	//OUT(k);//
	//if (sz(k,rt[k])!=r-l+1) puts("AFTER"),OUT(k),exit(0);
	if (l==r) return A[p]=v,void();
	int mid=l+r>>1;
	if (mid>=p) Modify(k<<1,l,mid,p,v);
	else Modify(k<<1|1,mid+1,r,p,v);
}
signed main(){
	///freopen("P3380_1.in","r",stdin);
	///freopen("A.out","w",stdout);
	n=read(),m=read();
	F(i,1,n) A[i]=read();
	Build(1,1,n);
	F(i,1,m){
		int op=read(),x=read(),y=read(),z;
		if (op==3) Modify(1,1,n,x,y);
		else{
			z=read();//printf("op = %d, ans = ",op);
			if (op==1) print(Queryrank(1,1,n,x,y,z)+1);else
			if (op==2) print(Queryk(x,y,z));else
			if (op==4) print(Querypre(1,1,n,x,y,z));else
			if (op==5) print(Querynxt(1,1,n,x,y,z));
		}
	}
	return 0;
}