Reincarnation

正因为梦易碎，才格外美好。

非旋式笛卡尔树

发表于 更新于 分类于 ，
本文字数： 18k 阅读时长 ≈ 17 分钟

撕裂中重组，烈火中重生。

浅谈笛卡尔树

笛卡尔树，也就是我们经常提及的一类平衡树，称为 ，其作用在于用堆的性质来维护一棵二叉搜索树的平衡性，使其达到期望下的 而不至于被卡成一条链。

也就是我们现在维护了一个数据结构同时满足堆与二叉搜索树的性质，这个数据结构后来被称为笛卡尔树，在平衡树板块中被称为 ，具体实现是维护一个二元组 ，对于 的左右儿子，满足 。也就是 维护 ，而 维护 。

而一般的平衡树而言，都是通过旋转来进行维护我们所需要的性质，这个步骤通过均摊可以做到 。而 的维护存在左旋与右旋之分，在书写的时候极容易出现错误，码量也会有一定的庞大，所以，我们考虑一个不需要旋转来维护的笛卡尔树。

非旋式笛卡尔树

在平衡树中又称 ，由范浩强发表的论文中提到的一个功能强大，常数始终，码量与理解难度较小的全能型平衡树。

参数

一般而言，以下的参数是必要的：

参数定义
 
1
2
3
4
5
6
#define ls(p) Tr[p].chi[0]
#define rs(p) Tr[p].chi[1]
struct Balanced
{
	int val,rd,siz,chi[2];
}Tr[MAXN];

其中 val 表示当前结点的权值，rd 表示当前结点的关键值（用于维护堆的性质），siz 为当前子树大小，而 chi[2] 则用于维护当前结点的左右儿子编号。

根据不同题目的要求，也可能会维护其它一些信息。

分裂

通过分裂与合并维护堆的平衡，这是与其它平衡树最本质的差别，而至于其他操作，就和其它平衡树一样，都可以通过这两个操作进行实现。

首先考虑分裂，一共有 种分裂方式，一个是按权值分裂，一个是按子树大小分裂，也就是将传入的参数 为根的一棵子树给分裂成两棵子树 ，其中可能会有 即按权值分裂，也可能是 是 中前 个，即按子树大小分裂。两种实现方式没有本质上的区别，只是需要在一些细节上进行修改即可。

按权值分裂参考实现
 
1
2
3
4
5
6
7
8
9
10
11
void split(int p,int k,int &u,int &v)
{
	if(!p) u=v=0;
	else
	{
		if(Tr[p].val<=k) u=p,split(rs(p),k,rs(p),v);
		else v=p,split(ls(p),k,u,ls(p));
		pushUp(p);
	}
	return ;
}
按子树大小分裂参考实现
 
1
2
3
4
5
6
7
8
9
10
11
void splitSiz(int p,int siz,int &u,int &v)
{
	if(!p) u=v=0;
	else
	{
		if(Tr[ls(p)].siz+1<=siz) u=p,split(rs(p),siz-Tr[ls(p)].siz-1,rs(p),v);
		else v=p,split(ls(p),siz,u,ls(p));
		return upDate(p);
	}
	return ;
}

唯一的区别在于，按照子树大小分裂向右走的时候需要减去左边子树的大小。

那么，执行上面的操作 split(p,k,x,y) 或者 splitSiz(p,k,x,y) 之后，我们会得到以下结果：

  1. 将以 为根的子树分裂成以 为根的子树，且 内权值不超过 。
  2. 将以 为根的子树分裂成以 为根的子树，且以 为根的子树大小为 。

所以这两步有什么用呢，我们之后再提及。

合并

按照 split 的操作，我们需要一个操作来让两棵子树合并起来，而这个合并的顺序首先要满足 BST，但我们又要整棵树尽可能平衡，所以合并的顺序按照 来划分。

参考实现
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int merge(int u,int v)
{
	if(!u||!v) return u^v;
	if(Tr[u].rd<Tr[v].rd)
	{
		rs(u)=merge(rs(u),v);
		return pushUp(u),u;
	}
	else
	{
		ls(v)=merge(u,ls(v));
		return pushUp(v),v;
	}
}

值得注意的是，这里的 merge 必须严格按照顺序合并，也就是我们传递的 必须在 BST 上合法，否则会产生难以弥补的错误。

其他操作

之后， 的所有操作都可以通过分裂合并来实现了。

插入

假若我们现在要插入一个权值为 的数，我们将整棵平衡树按权值从 分裂，把 视作一棵只有一个结点的子树，然后按照顺序合并三棵子树即可。

参考实现
 
1
2
3
4
5
6
7
8
9
10
11
inline int newNode(int v)
{
	Tr[++Idx]=(Balanced){v,rnd(),1};
	return Idx;
}
inline void insert(int v)
{
	int x=0,y=0;
	split(Rt,v,x,y);
	Rt=merge(merge(x,newNode(v)),y);
}

当然，也会存在很多我们需要传递的信息，视题目进行添加。

删除

值得注意的是，这里讨论的 维护的是一个不可重集，意味着某一个权值只能出现一次，这样的话，我们只需要将权值 从平衡树上抹去即可。

参考实现
 
1
2
3
4
5
6
7
inline void del(int v)
{
	int x=0,y=0,z=0;
	split(Rt,v,x,z),split(x,v-1,x,y);
	y=merge(ls(y),rs(y));
	Rt=merge(merge(x,y),z);
}

这里可以加入垃圾回收优化，多开一个垃圾桶进行记录即可。

参考实现
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Stk[MAXN],Top;
inline int newNode(int v)
{
	int id=Top?Stk[Top--]:++Idx;
	Tr[id]=(Balanced){v,rnd(),1,0,0};
	return id;
}
inline void del(int v)
{
	x=y=z=0;
	split(Rt,v,x,z);
	split(x,v-1,x,y);
	if(y)
	{
		if(Top<MAXN-10) Stk[++Top]=y;
		y=merge(ls(y),rs(y));
	}
	Rt=merge(merge(x,y),z);
}

查询排名上的值

也就是求出当前子树上的第 大值。按照线段树二分，或者是主席树那样的维护，向右子树跳的时候减去左子树即可。

参考实现
 
1
2
3
4
5
6
7
8
9
inline int kth(int p,int k)
{
	while(true)
	{
		if(k<=Tr[ls(p)].siz) p=ls(p);
		else if(k==Tr[ls(p)].siz+1) return p;
		else k-=Tr[ls(p)].siz+1,p=rs(p);
	}
}

如果这里引用出错，或者出现了违法现象，则很有可能导致死循环从而使代码出错。

查询排名上的值

也就是求出比 小的数的个数，因为是权值平衡树，所以可以直接求得：

参考实现
 
1
2
3
4
5
6
7
8
inline int rank(int v)
{
	int x=0,y=0;
	split(Rt,v-1,x,y);
	int res=Tr[x].siz+1;
	Rt=merge(x,y);
	return res;
}

前驱/后继

考虑利用 kth 进行解决这个问题，我们从 处分裂，那么 的前驱/后继就是前面子树的最后一个结点/后面子树的第一个结点。

参考实现
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline int pre(int v)
{
	int x=0,y=0;
	split(Rt,v-1,x,y);
	int res=Tr[kth(x,Tr[x].siz)].val;
	Rt=merge(x,y);
	return res;
}
inline int nxt(int v)
{
	int x=0,y=0;
	split(Rt,v,x,y);
	int res=Tr[kth(y,1)].val;
	Rt=merge(x,y);
	return res;
}

区间操作

区间操作的分裂方式有 种，其一是按照子树大小合并将整个区间提取为 三段，并对中间段进行操作。其二是将权值赋为该结点在序列中的位置，并依然通过权值进行分裂，第二种方式较为麻烦，所以我们这里讨论按子树大小进行分裂的做法。

平衡树和线段树本质相同，某位巨佬曾言。我们按照序列顺序读入平衡树，使得其中序遍历为原序列，然后进行子树提取即可，这个方式可以实现区间翻转（详见文艺平衡树），以及区间加区间最大子段和等等线段树可以维护的操作，也同样需要 pushdown 操作，添加在 split 和 merge 的递归之前即可。

一般情况都是这样来写：

参考实现
 
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
void split(int p,int siz,int &u,int &v)
{
	if(!p) u=v=0;
	else
	{
		pushDown(p);
		if(Tr[ls(p)].siz+1<=siz) u=p,split(rs(p),siz-Tr[ls(p)].siz-1,rs(p),v);
		else v=p,split(ls(p),siz,u,ls(p));
		upDate(p);
	}
	return ;
}
int merge(int u,int v)
{
	if(!u||!v) return u^v;
	else if(Tr[u].rd<Tr[v].rd)
	{
		pushDown(u);
		rs(u)=merge(rs(u),v);
		return upDate(u),u;
	}
	else
	{
		pushDown(v);
		ls(v)=merge(u,ls(v));
		return upDate(v),v;
	}
}
inline void reverse(int l,int r)
{
	int x=0,y=0,z=0;
	split(Rt,l-1,x,y);
	split(y,r-l+1,y,z);
	// upDate(y);
	Rt=merge(merge(x,y),z);
}

例题

普通平衡树

题目简介

维护一个序列的插入，删除，前取，后继，排名等。

评测链接：https://www.luogu.com.cn/problem/P3369

AC 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
// ----- Eternally question-----
// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-04-17 07:49:28
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
std::mt19937 rnd((ll)new char);
int Q;
struct Fhq
{
	#define ls(p) Tr[p].chi[0]
	#define rs(p) Tr[p].chi[1]
	int Idx,Rt;
	struct St
	{ int val,rd,siz,chi[2]; }Tr[MAXN];
	inline void pushUp(int p)
	{ Tr[p].siz=Tr[ls(p)].siz+Tr[rs(p)].siz+1; }
	inline int newNode(int v)
	{
		Tr[++Idx]=(St){v,(int)rnd(),1};
		return Idx;
	}
	inline void split(int p,int k,int &u,int &v)
	{
		if(!p) u=v=0;
		else
		{
			if(Tr[p].val<=k) u=p,split(rs(p),k,rs(p),v);
			else v=p,split(ls(p),k,u,ls(p));
			pushUp(p);
		}
		return ;
	}
	inline int merge(int u,int v)
	{
		if(!u||!v) return u^v;
		if(Tr[u].rd<Tr[v].rd)
		{
			rs(u)=merge(rs(u),v);
			return pushUp(u),u;
		}
		else
		{
			ls(v)=merge(u,ls(v));
			return pushUp(v),v;
		}
	}
	inline void insert(int v)
	{
		int x=0,y=0;
		split(Rt,v,x,y);
		Rt=merge(merge(x,newNode(v)),y);
	}
	inline void del(int v)
	{
		int x=0,y=0,z=0;
		split(Rt,v,x,z),split(x,v-1,x,y);
		y=merge(ls(y),rs(y));
		Rt=merge(merge(x,y),z);
	}
	inline int kth(int p,int k)
	{
		while(true)
		{
			if(k<=Tr[ls(p)].siz) p=ls(p);
			else if(k==Tr[ls(p)].siz+1) return p;
			else k-=Tr[ls(p)].siz+1,p=rs(p);
		}
	}
	inline int rank(int v)
	{
		int x=0,y=0;
		split(Rt,v-1,x,y);
		int res=Tr[x].siz+1;
		Rt=merge(x,y);
		return res;
	}
	inline int pre(int v)
	{
		int x=0,y=0;
		split(Rt,v-1,x,y);
		int res=Tr[kth(x,Tr[x].siz)].val;
		Rt=merge(x,y);
		return res;
	}
	inline int nxt(int v)
	{
		int x=0,y=0;
		split(Rt,v,x,y);
		int res=Tr[kth(y,1)].val;
		Rt=merge(x,y);
		return res;
	}
	#undef ls
	#undef rs
}Tr;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Q);
	for(int opt,qx;Q--;)
	{
		read(opt,qx);
		if(opt==1) Tr.insert(qx);
		else if(opt==2) Tr.del(qx);
		else if(opt==3) write(Tr.rank(qx),'\n');
		else if(opt==4) write(Tr.Tr[Tr.kth(Tr.Rt,qx)].val,'\n');
		else if(opt==5) write(Tr.pre(qx),'\n');
		else if(opt==6) write(Tr.nxt(qx),'\n');
	}
	return 0;
}
/*

*/

文艺平衡树

题目简介

实现区间翻转。

评测链接：https://www.luogu.com.cn/problem/P3391

我们刚刚提到过，如果把平衡树的中序遍历作为其序列位置的话，那么区间翻转就是让左右子树交换即可，需要 pushdown。

AC 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
// ----- Eternally question-----
// Problem: P3391 【模板】文艺平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3391
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-04-17 08:56:16
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
std::mt19937 rnd((ll)new char);
int N,Q;
struct Balanced
{
	#define ls(p) Tr[p].chi[0]
	#define rs(p) Tr[p].chi[1]
	int Idx,Rt,x,y,z;
	struct Treap
	{
		int chi[2],siz,val,rd;
		bool rev;
	}Tr[MAXN];
	inline void upDate(int p)
	{ Tr[p].siz=Tr[ls(p)].siz+Tr[rs(p)].siz+1; }
	inline void pushDown(int p)
	{
		if(!Tr[p].rev) return ;
		std::swap(ls(p),rs(p));
		Tr[ls(p)].rev^=1,Tr[rs(p)].rev^=1;
		Tr[p].rev^=1;
	}
	void split(int p,int siz,int &u,int &v)
	{
		if(!p) u=v=0;
		else
		{
			pushDown(p);
			if(Tr[ls(p)].siz+1<=siz) u=p,split(rs(p),siz-Tr[ls(p)].siz-1,rs(p),v);
			else v=p,split(ls(p),siz,u,ls(p));
			upDate(p);
		}
		return ;
	}
	int merge(int u,int v)
	{
		if(!u||!v) return u^v;
		else if(Tr[u].rd<Tr[v].rd)
		{
			pushDown(u);
			rs(u)=merge(rs(u),v);
			return upDate(u),u;
		}
		else
		{
			pushDown(v);
			ls(v)=merge(u,ls(v));
			return upDate(v),v;
		}
	}
	inline int newNode(int v)
	{
		Tr[++Idx]=(Treap){{0,0},1,v,(int)rnd(),0};
		return Idx;
	}
	inline void reverse(int l,int r)
	{
		x=y=z=0;
		split(Rt,l-1,x,y);
		split(y,r-l+1,y,z);
		Tr[y].rev^=1;
		Rt=merge(merge(x,y),z);
	}
	inline void init(int n)
	{ for(int i=1;i<=n;++i) Rt=merge(Rt,newNode(i)); }
	inline void print(int p)
	{
		if(!p) return ;
		pushDown(p);
		print(ls(p));
		write(Tr[p].val,' ');
		print(rs(p));
	}
	#undef ls
	#undef rs
}Tr;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	Tr.init(N);
	for(int ql,qr;Q--;)
	{
		read(ql,qr);
		Tr.reverse(ql,qr);
		// Tr.print(Tr.Rt);
		// puts("");
	}
	Tr.print(Tr.Rt);
	return 0;
}
/*

*/

平衡树的大部分运用

题目简介

题目名称：数列
题目来源：

评测链接：https://www.luogu.com.cn/problem/P2710

形式化题意：维护一个数列的插入，删除，翻转，和区间覆盖，求区间和，单点值，区间最大子段和（不能为空）。

数据范围：

就暴力维护即可，按照线段树那样进行维护即可，记得多进行 pushup 和 pushdown，然后注意子段和不为空即可。这道题有双倍经验，是 真题。

AC 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
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
275
276
277
278
279
280
281
282
283
284
285
286
// ----- Eternally question-----
// Problem: P2710 数列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2710
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-04-17 19:04:58
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
std::mt19937 rnd(114514+1919*810);
int N,Q;
struct Balanced
{
	#define ls(p) Tr[p].chi[0]
	#define rs(p) Tr[p].chi[1]
	int Rt,Idx,x,y,z;
	int Stk[MAXN],Top;
	struct Treap
	{
		int chi[2],siz,rd,cov;
		int val,sum,lsum,rsum,res;
		bool rev;
	}Tr[MAXN];
	inline void pushUp(int p)
	{
		Tr[p].siz=Tr[ls(p)].siz+Tr[rs(p)].siz+1;
		Tr[p].sum=Tr[ls(p)].sum+Tr[rs(p)].sum+Tr[p].val;
		if(ls(p)&&rs(p))
		{
			Tr[p].lsum=std::max(Tr[ls(p)].lsum,Tr[ls(p)].sum+Tr[rs(p)].lsum+Tr[p].val);
			Tr[p].rsum=std::max(Tr[rs(p)].rsum,Tr[rs(p)].sum+Tr[ls(p)].rsum+Tr[p].val);
			Tr[p].res=std::max(std::max(Tr[ls(p)].res,Tr[rs(p)].res),Tr[ls(p)].rsum+Tr[rs(p)].lsum+Tr[p].val);
		}
		else if(ls(p))
		{
			Tr[p].res=std::max(Tr[ls(p)].res,Tr[ls(p)].rsum+Tr[p].val);
			Tr[p].lsum=std::max(Tr[ls(p)].lsum,Tr[ls(p)].sum+Tr[p].val);
			checkMax(Tr[p].lsum,0);
			Tr[p].rsum=std::max(Tr[ls(p)].rsum+Tr[p].val,0);
		}
		else if(rs(p))
		{
			Tr[p].res=std::max(Tr[rs(p)].res,Tr[rs(p)].lsum+Tr[p].val);
			Tr[p].rsum=std::max(Tr[rs(p)].rsum,Tr[rs(p)].sum+Tr[p].val);
			checkMax(Tr[p].rsum,0);
			Tr[p].lsum=std::max(Tr[rs(p)].lsum+Tr[p].val,0);
		}
		else
		{
			Tr[p].res=Tr[p].sum;
			Tr[p].lsum=Tr[p].rsum=std::max(Tr[p].val,0);
		}
	}
	inline void Swap(int p)
	{
		std::swap(ls(p),rs(p));
		std::swap(Tr[p].lsum,Tr[p].rsum);
		Tr[p].rev^=1;
	}
	inline void upDate(int p,int c)
	{
		Tr[p].val=c,Tr[p].sum=Tr[p].siz*c;
		Tr[p].lsum=Tr[p].rsum=std::max(Tr[p].sum,0);
		Tr[p].res=std::max(Tr[p].sum,Tr[p].val);
		Tr[p].cov=c;
		return ;
	}
	inline void pushDown(int p)
	{
		if(Tr[p].rev)
		{
			if(ls(p)) Swap(ls(p));
			if(rs(p)) Swap(rs(p));
			Tr[p].rev=0;
		}
		if(Tr[p].cov!=-INF)
		{
			if(ls(p)) upDate(ls(p),Tr[p].cov);
			if(rs(p)) upDate(rs(p),Tr[p].cov);
			Tr[p].cov=-INF;
		}
	}
	inline int newNode(int v)
	{
		int id=Top?Stk[Top--]:++Idx;
		Tr[id].siz=1,Tr[id].rd=(int)rnd(),Tr[id].rev=0;
		Tr[id].cov=-INF,Tr[id].val=Tr[id].res=v;
		Tr[id].sum=v,Tr[id].chi[0]=Tr[id].chi[1]=0;
		Tr[id].lsum=Tr[id].rsum=std::max(v,0);
		return id;
	}
	void split(int p,int siz,int &u,int &v)
	{
		if(!p) u=v=0;
		else
		{
			pushDown(p);
			if(Tr[ls(p)].siz+1<=siz) u=p,split(rs(p),siz-Tr[ls(p)].siz-1,rs(p),v);
			else v=p,split(ls(p),siz,u,ls(p));
			pushUp(p);
		}
		return ;
	}
	int merge(int u,int v)
	{
		if(u) pushDown(u);
		if(v) pushDown(v);
		if(!u||!v) return u^v;
		else if(Tr[u].rd<Tr[v].rd)
		{
			rs(u)=merge(rs(u),v);
			return pushUp(u),u;
		}
		else
		{
			ls(v)=merge(u,ls(v));
			return pushUp(v),v;
		}
	}
	inline void insert(int p,int n)
	{
		x=y=0;
		split(Rt,p,x,y);
		for(int qx;n--;)
		{
			read(qx);
			x=merge(x,newNode(qx));
		}
		Rt=merge(x,y);
	}
	inline void erase(int p)
	{
		if(!p) return ;
		Stk[++Top]=p;
		erase(ls(p)),erase(rs(p));
	}
	inline void del(int p,int n)
	{
		x=y=z=0;
		split(Rt,p-1,x,y),split(y,n,y,z);
		erase(y);
		Rt=merge(x,z);
	}
	inline void reverse(int p,int n)
	{
		x=y=z=0;
		split(Rt,p-1,x,y),split(y,n,y,z);
		Swap(y);
		Rt=merge(merge(x,y),z);
	}
	inline void cover(int p,int n,int c)
	{
		x=y=z=0;
		split(Rt,p-1,x,y),split(y,n,y,z);
		upDate(y,c);
		Rt=merge(merge(x,y),z);
	}
	inline int getSum(int p,int n)
	{
		x=y=z=0;
		split(Rt,p-1,x,y),split(y,n,y,z);
		int res=Tr[y].sum;
		Rt=merge(merge(x,y),z);
		return res;
	}
	inline int getX(int p)
	{
		x=y=z=0;
		split(Rt,p-1,x,y),split(y,1,y,z);
		int res=Tr[y].val;
		Rt=merge(merge(x,y),z);
		return res;
	}
	inline int getMaxsum(int p,int n)
	{
		x=y=z=0;
		split(Rt,p-1,x,y),split(y,n,y,z);
		int res=Tr[y].res;
		Rt=merge(merge(x,y),z);
		return res;
	}
	inline void init(int n)
	{
		for(int x;n--;) read(x),Rt=merge(Rt,newNode(x));
	}
	inline void print(int p)
	{
		if(!p) return ;
		pushDown(p);
		print(ls(p));
		write(Tr[p].val,' ');
		print(rs(p));
	}
	#undef ls
	#undef rs
}Tr;
char Opt[20];
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	Tr.init(N);
	while(Q--)
	{
		scanf("%s",Opt);
		if(Opt[0]=='I')
		{
			int p,n;read(p,n);
			Tr.insert(p,n);
		}
		else if(Opt[0]=='D')
		{
			int p,n;read(p,n);
			Tr.del(p,n);
		}
		else if(Opt[0]=='R')
		{
			int p,n;read(p,n);
			Tr.reverse(p,n);
		}
		else if(Opt[2]=='K')
		{
			int p,n,c;read(p,n,c);
			Tr.cover(p,n,c);
		}
		else if(Opt[0]=='G'&&std::strlen(Opt)>3)
		{
			int p,n;read(p,n);
			write(Tr.getSum(p,n),'\n');
		}
		else if(Opt[0]=='G')
		{
			int p;read(p);
			write(Tr.getX(p),'\n');
		}
		else
		{
			int p,n;read(p,n);
			write(Tr.getMaxsum(p,n),'\n');
		}
	}
	return 0;
}
/*

*/

相关文章