avatar

Fu Yaogang

Undergraduate student majoring in Computer Science and Technology at Beijing Forestry University.

My Data Structures Code Template

前缀和

二维

1
2
3
4
5
for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

三维以及更高维

$s[i][j][k]=a[i][j][k]+s[i][j][k-1]+s[i][j-1][k]-s[i][j-1][k-1]\+s[i-1][j][k]-s[i-1][j][k-1]-s[i-1][j-1][k]+s[i-1][j-1][k-1]$

$s=s[x_2][y_2][z_2]-s[x_2][y_2][z_1-1]-s[x_2][y_1-1][z_2]+s[x_2][y_1-1][z_1-1]\-s[x_1-1][y_2][z_2]+s[x_1-1][y_2][z_1-1]+s[x_1-1][y_1-1][z_2]-s[x_1-1][y_1-1][z_1-1]$

预处理时 $i-1$ ，$j-1$ ，$k-1$ 均代表 $1$ 而 $i$ ，$j$ ，$k$ 都代表 $0$ 。

当其二进制数中有奇数个 $1$ 时该项为正，偶数个 $1$ 时该项为负。

用 $x_2$，$y_2$，$z_2$ 代表 $0$ ，$x_1-1$，$y_1-1$，$z_1-1$ 代表 $1$

其与预处理则是相反的，有奇数个1时该项为负，偶数个1时该项为正

差分

1
2
3
4
5
6
7
8
9
10
void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

逆序对数量（归并）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int tmp[N];
int merge_sort(int q[], int l, int r){	//q数组[l,r]范围内逆序对个数
	if(l >= r) return 0;
	int mid = l + r >> 1;
	int res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
	
	int k = 0, i = l, j = mid + 1;
	while(i <= mid && j <= r){
		if(q[i] <= q[j]) tmp[k++] = q[i++];
		else res += mid - i + 1, tmp[k++] = q[j++];
	}
	while(i <= mid) tmp[k++] = q[i++];
	while(j <= r) tmp[k++] = q[j++];
	for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
	return res;
}

单调栈

1
2
3
4
5
6
7
8
9
10
11
int res[N], sz;	//q数组[l,r]范围中每个数左边第一个比它小的数的下标，不存在则为-1
void calc(int a[], int l, int r){
	static int sta[N], tp = 0;
	sz = 0;
	for(int i = l; i <= r; i++){
		while(tp && a[sta[tp]] >= a[i]) tp--;
		if(!tp) res[++sz] = -1;
		else res[++sz] = sta[tp];
		sta[++tp] = i;
	}
}

单调队列

1
2
3
4
5
6
7
8
9
10
11
int res[N], sz;	//q数组[l,r]范围中每个位置长度为k的窗口中的最小值下标，sz最终为(r - l + 1 - k + 1)
void calc(int a[], int l, int r, int k){
	static int q[N], hh = 0, tt = -1;
	sz = 0;
	for(int i = l; i <= r; i++){
		if(hh <= tt && q[hh] < i - k + 1) hh++;
		while(hh <= tt && a[q[tt]] >= a[i]) tt--;	//改成a[q[tt]]<=a[i]就是求最大值
		q[++tt] = i;
		if(i >= l + k - 1) res[++sz] = q[hh];
	}
}

LCA

  • $u,v$ ：求 $lca(u,v)$
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
int n, m, root;
int h[N], e[M], ne[M], idx;
int dep[N], fa[N][K];

void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u){
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i];
		if(j == fa[u][0]) continue;
		dep[j] = dep[u] + 1;
		fa[j][0] = u;
		for(int k = 1; k < K; k++){
			fa[j][k] = fa[fa[j][k - 1]][k - 1];
		}
		dfs(j);
	}
}

int lca(int u, int v){
	if(dep[u] > dep[v]) swap(u, v);
	for(int k = K - 1; k >= 0; k--){
		if(dep[u] <= dep[fa[v][k]]){
			v = fa[v][k];
		}
	}
	if(u == v) return u;
	for(int k = K - 1; k >= 0; k--){
		if(fa[u][k] != fa[v][k]){
			u = fa[u][k], v = fa[v][k];
		}
	}
	return fa[u][0];
}

void solve(){
	cin >> n >> m >> root;
	memset(h, -1, sizeof(int) * (n + 1));
	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		add(a, b), add(b, a);
	}
	dep[root] = 1;	//不能忘，root的深度不能与0的深度相同
	dfs(root);
	while(m--){
		int a, b; cin >> a >> b;
		cout << lca(a, b) << '\n';
	}
}

字典树（树上最长异或路径）

  • $max(f(i,j)),i\in[1,n],j\in[1,n],f(i,j)=a[i]\oplus\dots a[j]$
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
class trie{
	const int K = 30;
private:
	struct node{
		int s[2];
		int w, cnt;
		void init(int w_ = 0, int cnt_ = 0){
			s[0] = s[1] = 0;
			w = w_, cnt = cnt_;
		}
	};
	vector<node> tr;
	int root, sz;
	
	int malloc(){
		int u = ++sz;
		tr[u].init();
		return u;
	}
	
	void pu(int u){
		tr[u].cnt = tr[tr[u].s[0]].cnt + tr[tr[u].s[1]].cnt;
	}
	
	void insert(int u, int k, int cnt, int i){
		if(i == -1){
			tr[u].w = k;
			tr[u].cnt += cnt;
			return;
		}
		else{
			bool c = k >> i & 1;
			if(!tr[u].s[c]) tr[u].s[c] = malloc();
			insert(tr[u].s[c], k, cnt, i - 1);
			pu(u);
		}
	}
	
	int query(int u, int k, int i){
		if(i == -1) {
			return tr[u].w; 
		}
		bool c = k >> i & 1;
		if(tr[tr[u].s[c ^ 1]].cnt) return query(tr[u].s[c ^ 1], k, i - 1);
		else return query(tr[u].s[c], k, i - 1);
	}
	
public:
	trie(int n){
		tr.resize(n * (K + 3));
		clear();
	}
	
	void insert(int k, int cnt){
		insert(root, k, cnt, K);
	}
	
	int query(int k){	//返回最大异或对的异或和
		return query(root, k, K) ^ k;
	}
	
	void clear(){
		tr[0].init(), sz = 0, root = malloc();
	}
};

int n;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];

void add(int a, int b, int c){
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa){
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i];
		if(j == fa) continue;
		dist[j] = dist[u] ^ w[i];
		dfs(j, u);
	}
}

void solve(){
	memset(h, -1, sizeof h);
	cin >> n;
	for(int i = 1; i < n; i++){
		int a, b, c; cin >> a >> b >> c;
		add(a, b, c), add(b, a, c);
	}
	dfs(1, 0);
	int res = 0;
	
	trie tr(n);
	for(int i = 1; i <= n; i++){
		tr.insert(dist[i], 1);
		res = max(res, tr.query(dist[i]));
	}
	cout << res << '\n';
}

可持久化字典树（最大异或和）

  • $A,x$ ：$n = n + 1, a[n] = x$
  • $Q,l,r,x$ ：$max(a[p]\oplus a[p+1]\dots \oplus a[n]),p\in[l,r]$
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
class ptrie{
	const int K = 24;
private:
	struct node{
		int s[2];
		int max_p, w;
		void init(int p = -1, int w_ = 0){
			s[0] = s[1] = 0;
			max_p = -1, w = 0;
		}
	};
	vector<node> tr;
	vector<int> root;
	int sz;
	
	int malloc(){
		int u = ++sz;
		tr[u].init();
		return u;
	}
	
	void pu(int u){
		tr[u].max_p = max(tr[tr[u].s[0]].max_p, tr[tr[u].s[1]].max_p);
	}
	
	int insert(int p, int x, int k, int i){
		int u = malloc();
		tr[u] = tr[p];
		if(i == -1){
			tr[u].max_p = x;
			tr[u].w = k;
		}
		else{
			bool c = k >> i & 1;
			tr[u].s[c] = insert(tr[u].s[c], x, k, i - 1);
			pu(u);
		}
		return u;
	}
	
	int query(int u, int l, int k, int i){
		if(i == -1) {
			return tr[u].w; 
		}
		bool c = k >> i & 1;
		if(tr[tr[u].s[c ^ 1]].max_p >= l) return query(tr[u].s[c ^ 1], l, k, i - 1);
		else return query(tr[u].s[c], l, k, i - 1);
	}
	
public:
	ptrie(int n){
		tr.resize(n * (K + 3));
		root.resize(n + 5);
		clear();
	}
	
	void copy(int v, int old){
		root[v] = root[old];
	}
	
	void insert(int v, int x, int k){
		root[v] = insert(root[v], x, k, K);
	}
	
	int query(int l, int r, int k){	//返回下标在l-r范围内的最大异或对的异或和
		return query(root[r], l, k, K) ^ k;
	}
	
	void clear(){
		tr[0].init(), sz = 0, root[0] = malloc();
	}
};

int n, m;
int a[N];
int xs[N];

void solve(){
	cin >> n >> m;
	ptrie tr(n + m + 5);
	for(int i = 1; i <= n; i++) cin >> a[i], xs[i] = xs[i - 1] ^ a[i];
	tr.insert(0, 0, 0);
	for(int i = 1; i <= n; i++){
		tr.copy(i, i - 1);
		tr.insert(i, i, xs[i]);
	}
	while(m--){
		char op; cin >> op;
		if(op == 'A'){
			int x; cin >> x;
			n++;
			xs[n] = xs[n - 1] ^ x;
			tr.copy(n, n - 1);
			tr.insert(n, n, xs[n]);
		}
		else{
			int l, r, x; cin >> l >> r >> x;
			cout << tr.query(l - 1, r - 1, xs[n] ^ x) << '\n';
		}
	}
}

并查集（路径压缩）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class dsu{
private:
	vector<int> p;
	
public:
	dsu(int n){
		p = vector<int>(n + 1, 0);
		iota(p.begin(), p.end(), 0);
	}
	
	int find(int x){
		if(p[x] != x) p[x] = find(p[x]);
		return p[x];
	}
	
	void merge(int x, int y){
		int px = find(x), py = find(y);
		if(px != py){
			p[px] = py;
		}
	}
};

按秩合并（可撤销并查集）

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
class qdsu{
private:
	struct edge{
		int x, y, hy;
	};
	vector<edge> sta;
	int tp;
	vector<int> p, h;
	
public:
	qdsu(int n){
		p = vector<int>(n + 1, 0);
		iota(p.begin(), p.end(), 0);
		h = vector<int>(n + 1, 0);
		sta.resize(n + 1);
		tp = 0;
	}
	
	int find(int x){
		if(p[x] == x) return x;
		return find(p[x]);
	}
	
	void merge(int x, int y){
		x = find(x), y = find(y);
		if(h[x] > h[y]) swap(x, y);
		p[x] = y;
		h[y] += (h[x] == h[y]);
		sta[tp++] = {x, y, h[y]};
	}
	
	void quash(){
		if(!tp) return;
		edge t = sta[--tp];
		h[t.y] = t.hy;
		p[t.x] = t.x;
	}
	
	int top(){
		return tp;
	}
};

可持久化并查集

  • $1,a,b$ ：$merge(a,b)$
  • $2,k$ ：回到第 $k$ 次操作
  • $3,a,b$ ：查询 $a,b$ 是否在同一集合
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
class parr;

class pdsu{
private:
	parr fa, sz;
	
public:
	pdsu(int n, int m):fa(n + m + 5), sz(n + m + 5){
		for(int i = 1; i <= n; i++){
			fa.modify(0, i, i);
			sz.modify(0, i, 1);
		}
	}
	
	int find(int v, int x){
		if(fa.query(v, x) == x) return x;
		return find(v, fa.query(v, x));
	}
	
	void merge(int v, int x, int y){
		x = find(v, x), y = find(v, y);
		if(x == y) return;
		int sx = sz.query(v, x), sy = sz.query(v, y);
		if(sx < sy) swap(x, y), swap(sx, sy);
		fa.modify(v, y, x);
		sz.modify(v, x, sx + sy);
	}
	
	bool equal(int v, int x, int y){
		return find(v, x) == find(v, y);
	}
	
	void copy(int v, int old){
		fa.copy(v, old);
		sz.copy(v, old);
	}
};

int n, m;

void solve(){
	cin >> n >> m;
	pdsu d(n, m);
	for(int i = 1; i <= m; i++){
		int op; cin >> op;
		d.copy(i, i - 1);
		if(op == 1){
			int a, b; cin >> a >> b;
			d.merge(i, a, b);
		}
		else if(op == 2){
			int k; cin >> k;
			d.copy(i, k);
		}
		else{
			int a, b; cin >> a >> b;
			cout << d.equal(i, a, b) << '\n';
		}
	}
}

线段树分治

  • $x,y,l,r$ ：有一条连接 $x,y$ 的边在 $l$ 时刻出现，$r$ 时刻消失
  • 询问：第 $i$ 时间段内图是否是二分图
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
class qdsu;

int n, m, k;
qdsu d(N * 2);
pii segs[N];

class seg{
public:
	struct node{
		int l, r;
		vector<int> id;
	};
	
private:
	vector<node> tr;
	
public:
	seg(int n){
		tr.resize(n * 4 + 10);
	}
	
	void build(int u, int l, int r){
		tr[u] = {l, r};
		if(l == r){
			return;
		}
		int mid = l + r >> 1;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	}
	
	void modify(int u, int l, int r, int k){
		if(l <= tr[u].l && tr[u].r <= r){
			node &o = tr[u];
			o.id.pb(k);
		}
		else{
			int mid = tr[u].l + tr[u].r >> 1;
			if(l <= mid) modify(u << 1, l, r, k);
			if(r > mid) modify(u << 1 | 1, l, r, k);
		}
	}
	
	void query(int u, int l, int r){
		int cur_tp = d.top();
		bool ok = 1;
		for(int id : tr[u].id){
			auto[x, y] = segs[id];
			int fx = d.find(x), fy = d.find(y);
			if(fx == fy){
				for(int i = l; i <= r; i++){
					cout << "No" << '\n';
				}
				ok = 0;
				break;
			}
			d.merge(x, y + n), d.merge(y, x + n);
		}
		if(ok){
			if(l == r) cout << "Yes" << '\n';
			else{
				int mid = l + r >> 1;
				query(u << 1, l, mid), query(u << 1 | 1, mid + 1, r);
			}
		}
		while(d.top() > cur_tp){
			d.quash();
		}
	}
};

seg tr(N);

void solve(){
	cin >> n >> m >> k;
	tr.build(1, 1, k);
	for(int i = 1; i <= m; i++){
		int x, y, l, r; cin >> x >> y >> l >> r;
		segs[i] = {x, y};
		tr.modify(1, l + 1, r, i);
	}
	tr.query(1, 1, k);
}

字符串哈希

  • hash_init() ：初始化 p 数组
  • hash_str.substr(l, r) ：获得子串 $[l,r]$
  • hash_substr + hash_substr ：拼接子串
  • hash_substr.rev() ：翻转子串
  • hash_substr == hash_substr ：判断子串是否相等
  • 注意，初始字符串要在最前方补一个空格，变成下标从 1 起
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
const int N = 2e6 + 10, M = N * 2, P = 998244353, inf = 2e18;

const int SP = 13331, M1 = 1e9 + 7, M2 = 1e9 + 21;
int p1[N], p2[N];
void hash_init(){
	p1[0] = p2[0] = 1;
	for(int i = 1; i < N; i++){
		p1[i] = p1[i - 1] * SP % M1;
		p2[i] = p2[i - 1] * SP % M2;
	}
}

class hash_str{
public:
	struct hash_substr{
		int h1, h2, rh1, rh2;
		int sz;
		
		hash_substr rev(){
			return {
				rh1, rh2, h1, h2, sz
			};
		}
		
		hash_substr operator+(hash_substr r){
			return {
				(h1 * p1[r.sz] + r.h1) % M1,
				(h2 * p2[r.sz] + r.h2) % M2,
				(r.rh1 * p1[sz] + rh1) % M1,
				(r.rh2 * p2[sz] + rh2) % M2,
				sz + r.sz
			};
		}
		
		bool operator==(hash_substr r)const{
			return h1 == r.h1 && h2 == r.h2 && rh1 == r.rh1 && rh2 == r.rh2 && sz == r.sz;
		}
		
		bool operator<(hash_substr r)const{
			if(h1 != r.h1) return h1 < r.h1;
			if(h2 != r.h2) return h2 < r.h2;
			if(rh1 != r.rh1) return rh1 < r.rh1;
			if(rh2 != r.rh2) return rh2 < r.rh2;
			return sz < r.sz;
		}
	};
	
private:
	int n;
	vector<int> f1, f2;
	vector<int> rf1, rf2;
	
	void getf(string &s, vector<int> &f, int M){
		f = vector<int>(s.size(), 0);
		for(int i = 1; i <= n; i++){
			f[i] = (f[i - 1] * SP + s[i]) % M;
		}
	}
	
	int geth(vector<int> &f, int *p, int l, int r, int M){
		return (f[r] + M - f[l - 1] * p[r - l + 1] % M) % M;
	}
	
public:
	hash_str(string s){
		n = s.size() - 1;
		getf(s, f1, M1), getf(s, f2, M2);
		s.push_back(' '), reverse(s.begin(), s.end()), s.pop_back();
		getf(s, rf1, M1), getf(s, rf2, M2);
	}
	
	hash_substr substr(int l, int r){
		if(l > r){
			return {0, 0, 0, 0, 0};
		}
		return {
			geth(f1, p1, l, r, M1),
			geth(f2, p2, l, r, M2),
			geth(rf1, p1, n - r + 1, n - l + 1, M1),
			geth(rf2, p2, n - r + 1, n - l + 1, M2),
			r - l + 1
		};
	}
};

void solve(){
	hash_init();
	int n; cin >> n;
	string s; cin >> s;
	s = " " + s;
	hash_str hs = s;
	
	for(int i = 0; i <= n; i++){
		auto s1 = hs.substr(1, i) + hs.substr(i + n + 1, n + n), s2 = hs.substr(i + 1, i + n).rev();
		if(s1 == s2){
			string res = s.substr(i + 1, n);
			reverse(res.begin(), res.end());
			cout << res << '\n' << i;
			return;
		}
	}
	cout << -1 << '\n';
}

树状数组

  • $x,c$ ：$a[x]=a[x]+c$
  • $l,r$ ：$\sum a[l,r]$
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
class bi{
private:
	int n;
	vector<int> tr;
	
	int lb(int x){
		return x & -x;
	}
	
public:
	bi(int n_){
		n = n_;
		tr = vector<int>(n + 1, 0);
	}
	
	void add(int x, int c){
		if(x == 0) tr[0] += c;
		else{
			for(int i = x; i <= n; i += lb(i)){
				tr[i] += c;
			}	
		}
	}
	
	int sum(int x){
		if(x < 0) return 0;
		int res = tr[0];
		for(int i = x; i; i -= lb(i)) res += tr[i];
		return res;
	}
	
	int sum(int l, int r){
		return sum(r) - sum(l - 1);
	}
	
	void clear(){
		fill(tr.begin(), tr.end(), 0);
	}
};

二维树状数组

单点修改，子矩阵查询

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
class bi2{
private:
	int n, m;
	vector<vector<int>> tr;
	
	int lb(int x){
		return x & -x;
	}
	
	int sum(int x, int y){
		int res = 0;
		for(int i = x; i; i -= lb(i)){
			for(int j = y; j; j -= lb(j)){
				res += tr[i][j];
			}
		}
		return res;
	}
	
public:
	bi2(int n_, int m_){
		n = n_, m = m_;
		tr = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
	}
	
	void add(int x, int y, int c){
		for(int i = x; i <= n; i += lb(i)){
			for(int j = y; j <= m; j += lb(j)){
				tr[i][j] += c;
			}
		}
	}
	
	int sum(int a, int b, int c, int d){
		return sum(c, d) - sum(c, b - 1) - sum(a - 1, d) + sum(a - 1, b - 1);
	}
	
	void clear(){
		for(auto &t : tr){
			for(auto &e : t){
				e = 0;
			}
		}
	}
};

子矩阵修改，子矩阵查询

  • $a,b,c,d,v$ ：$a[a,c][b,d]=a[a,c][b,d]+v$
  • $a,b,c,d$ ：$\sum a[a,c][b,d]$
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
class bi2{
private:
	int n, m;
	vector<vector<int>> tr[4];
	
	int lb(int x){
		return x & -x;
	}
	
	void add(int x, int y, int c){
		int v[] = {c, x * c, y * c, x * y * c};
		for(int i = x; i <= n; i += lb(i)){
			for(int j = y; j <= m; j += lb(j)){
				for(int k = 0; k < 4; k++){
					tr[k][i][j] += v[k];
				}
			}
		}
	}
	
	int sum(int x, int y){
		int s[] = {0, 0, 0, 0};
		for(int i = x; i; i -= lb(i)){
			for(int j = y; j; j -= lb(j)){
				for(int k = 0; k < 4; k++){
					s[k] += tr[k][i][j];
				}
			}
		}
		return (x + 1) * (y + 1) * s[0] - (y + 1) * s[1]
		- (x + 1) * s[2] + s[3];
	}
	
public:
	bi2(int n_, int m_){
		n = n_, m = m_;
		for(int k = 0; k < 4; k++){
			tr[k] = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
		}
	}
	
	void add(int a, int b, int c, int d, int v){
		add(a, b, v), add(c + 1, b, -v);
		add(a, d + 1, -v), add(c + 1, d + 1, v);
	}
	
	int sum(int a, int b, int c, int d){
		return sum(c, d) + sum(a - 1, b - 1) - sum(a - 1, d) - sum(c, b - 1);
	}
	
	void clear(){
		for(int k = 0; k < 4; k++){
			for(auto &t : tr[k]){
				for(auto &e : t){
					e = 0;
				}
			}
		}
	}
};

线段树（区间修改+区间查询）

  • $1,x,y,k$ ：$a[x,y]=a[x,y]+k$
  • $2,x,y$ ： $\sum a[x,y]$
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
class seg{
private:
	struct node{
		int l, r;
		int sum;
		int add;
	};
	vector<node> tr;
    
public:
	seg(int n){
		tr.resize(n * 4 + 10);
	}
    
    void build(int u, int l, int r){
		if(l == r){
			tr[u] = {l, r, 0, 0};
		}
		else{
			tr[u] = {l, r};
			int mid = l + r >> 1;
			build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
			pu(u);
		}
	}
	
	node friend operator + (node l, node r){
		node o;
		o.l = l.l, o.r = r.r;
		o.add = 0;
		o.sum = l.sum + r.sum;
		return o;
	}
	
	void pu(int u){
		tr[u] = tr[u << 1] + tr[u << 1 | 1];
	}
	
	void pd(int u){
		node &o = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
		if(o.add){
			l.add += o.add, r.add += o.add;
			l.sum += (l.r - l.l + 1) * o.add, r.sum += (r.r - r.l + 1) * o.add;
			o.add = 0;
		}
	}
	
	void modify(int u, int l, int r, int k){
		if(l <= tr[u].l && tr[u].r <= r){
			node &o = tr[u];
			o.sum += (o.r - o.l + 1) * k;
			o.add += k;
		}
		else{
			pd(u);
			int mid = tr[u].l + tr[u].r >> 1;
			if(l <= mid) modify(u << 1, l, r, k);
			if(r > mid) modify(u << 1 | 1, l, r, k);
			pu(u);
		}
	}
	
	node query(int u, int l, int r){
		if(l <= tr[u].l && tr[u].r <= r){
			return tr[u];
		}
		else{
			pd(u);
			int mid = tr[u].l + tr[u].r >> 1;
			if(r <= mid) return query(u << 1, l, r);
			if(l > mid) return query(u << 1 | 1, l, r);
			return query(u << 1, l, r) + query(u << 1 | 1, l, r);
		}
	}
};

线段树（最大子段和）

  • $0,x,k$ ：$a[x]=k$
  • $1,l,r$ ：查询 $a[l,r]$ 最大子段和
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
class seg{
private:
	struct node{
		int l, r;
		int ls, rs, ms;
		int sum;
	};
	vector<node> tr;
    
public:
	seg(int n){
		tr.resize(n * 4 + 10);
	}
    
    void build(int u, int l, int r){
		if(l == r){
			tr[u] = {l, r, 0, 0, 0, 0};
		}
		else{
			tr[u] = {l, r};
			int mid = l + r >> 1;
			build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
			pu(u);
		}
	}
	
	node friend operator + (node l, node r){
		node o;
		o.l = l.l, o.r = r.r;
		o.ls = max(l.ls, l.sum + r.ls);
		o.rs = max(r.rs, r.sum + l.rs);
		o.ms = max({l.ms, r.ms, l.rs + r.ls});
		o.sum = l.sum + r.sum;
		return o;
	}
	
	void pu(int u){
		tr[u] = tr[u << 1] + tr[u << 1 | 1];
	}
	
	void modify(int u, int x, int k){
		if(x <= tr[u].l && tr[u].r <= x){
			node &o = tr[u];
			o = {x, x, k, k, k, k};
		}
		else{
			int mid = tr[u].l + tr[u].r >> 1;
			if(x <= mid) modify(u << 1, x, k);
			else modify(u << 1 | 1, x, k);
			pu(u);
		}
	}
	
	node query(int u, int l, int r){
		if(l <= tr[u].l && tr[u].r <= r){
			return tr[u];
		}
		else{
			int mid = tr[u].l + tr[u].r >> 1;
			if(r <= mid) return query(u << 1, l, r);
			if(l > mid) return query(u << 1 | 1, l, r);
			return query(u << 1, l, r) + query(u << 1 | 1, l, r);
		}
	}
};

可持久化数组

  • $old,1,x,k$ ：$old$ 版本 $a_{x} = k$
  • $old,2,x$ ：查询 $old$ 版本 $a_x$
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
class parr{
private:
	struct node{
		int s[2];
		int w;
		void init(int w_ = 0){
			s[0] = s[1] = 0;
			w_ = w;
		}
	};
	
	vector<node> tr;
	vector<int> root;
	int sz;
	int L, R;
	
	int malloc(){
		int u = ++sz;
		tr[u].init();
		return u;
	}
	
	void pu(int u){}
	
	int modify(int p, int x, int k, int L, int R){
		int u = malloc();
		tr[u] = tr[p];
		if(L == R){
			tr[u].w = k;
		}
		else{
			int mid = L + R >> 1;
			if(x <= mid) tr[u].s[0] = modify(tr[u].s[0], x, k, L, mid);
			else tr[u].s[1] = modify(tr[u].s[1], x, k, mid + 1, R);
			pu(u);
		}
		return u;
	}
	
	int query(int u, int x, int L, int R){
		if(L == R){
			return tr[u].w;
		}
		else{
			int mid = L + R >> 1;
			if(x <= mid) return query(tr[u].s[0], x, L, mid);
			else return query(tr[u].s[1], x, mid + 1, R);
		}
	}
	
public:
	parr(int n){
		tr.resize(n * 25);
		root.resize(n);
		L = 1, R = n;
		clear();
	}
	
	void clear(){
		tr[0].init(), sz = 0, root[0] = malloc();
	}
	
	void copy(int v, int old){
		root[v] = root[old];
	}
	
	void modify(int v, int x, int k){
		root[v] = modify(root[v], x, k, L, R);
	}
	
	int query(int v, int x){
		return query(root[v], x, L, R);
	}
};

主席树（静态区间第K小）

序列

  • $l,r,k$ ：$a[l,r]$ 第 $k$ 小的数，$k\in [1,r-l+1]$
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
class pseg{
private:
	struct node{
		int s[2];
		int w, cnt;
		void init(int w_ = 0, int cnt_ = 0){
			s[0] = s[1] = 0;
			w = w_, cnt = cnt_;
		}
	};
	
	vector<node> tr;
	vector<int> root;
	int sz;
	int L, R;
	
	int malloc(){
		int u = ++sz;
		tr[u].init();
		return u;
	}
	
	void pu(int u){
		tr[u].cnt = tr[tr[u].s[0]].cnt + tr[tr[u].s[1]].cnt;
	}
	
	int modify(int p, int x, int k, int L, int R){
		int u = malloc();
		tr[u] = tr[p];
		if(L == R){
			tr[u].w = x;
			tr[u].cnt += k;
		}
		else{
			int mid = L + R >> 1;
			if(x <= mid) tr[u].s[0] = modify(tr[u].s[0], x, k, L, mid);
			else tr[u].s[1] = modify(tr[u].s[1], x, k, mid + 1, R);
			pu(u);
		}
		return u;
	}
	
	int query(int p, int u, int k, int L, int R){
		if(L == R){
			return L;
		}
		else{
			int mid = L + R >> 1;
			int cnt = tr[tr[u].s[0]].cnt - tr[tr[p].s[0]].cnt;
			if(cnt >= k) return query(tr[p].s[0], tr[u].s[0], k, L, mid);
			else return query(tr[p].s[1], tr[u].s[1], k - cnt, mid + 1, R);
		}
	}
	
public:
	pseg(int n){
		tr.resize(n * 25);
		root.resize(n);
		L = 1, R = n;
		clear();
	}
	
	void clear(){
		tr[0].init(), sz = 0, root[0] = malloc();
	}
	
	void copy(int v, int old){
		root[v] = root[old];
	}
	
	void modify(int v, int x, int k){
		root[v] = modify(root[v], x, k, L, R);
	}
	
	int query(int l, int r, int k){
		return query(root[l - 1], root[r], k, L, R);
	}
};

int n, m;

vector<int> nums;
int f(int x){
	return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

int a[N];

void solve(){
	cin >> n >> m;
	nums.pb(-inf);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		nums.pb(a[i]);
	}
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	
	int t = nums.size() - 1;
	
	pseg tr(n + 5);
	for(int i = 1; i <= n; i++){
		tr.copy(i, i - 1);
		tr.modify(i, f(a[i]), 1);
	}
	while(m--){
		int l, r, k; cin >> l >> r >> k;
		cout << nums[tr.query(l, r, k)] << '\n';
	}
}

树上

  • $u,v,k$ ：$tr[u,v]$ 上第 $k$ 小，$k\in [1,len_{u,v}]$
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
int a[N];

int n, m;
int h[N], e[M], ne[M], idx;
int dep[N], fa[N][K];

int lca(int u, int v);

class pseg{
private:
	struct node{
		int s[2];
		int w, cnt;
		void init(int w_ = 0, int cnt_ = 0){
			s[0] = s[1] = 0;
			w = w_, cnt = cnt_;
		}
	};
	
	vector<node> tr;
	vector<int> root;
	int sz;
	int L, R;
	
	int malloc(){
		int u = ++sz;
		tr[u].init();
		return u;
	}
	
	void pu(int u){
		tr[u].cnt = tr[tr[u].s[0]].cnt + tr[tr[u].s[1]].cnt;
	}
	
	int modify(int p, int x, int k, int L, int R){
		int u = malloc();
		tr[u] = tr[p];
		if(L == R){
			tr[u].w = x;
			tr[u].cnt += k;
		}
		else{
			int mid = L + R >> 1;
			if(x <= mid) tr[u].s[0] = modify(tr[u].s[0], x, k, L, mid);
			else tr[u].s[1] = modify(tr[u].s[1], x, k, mid + 1, R);
			pu(u);
		}
		return u;
	}
	
	int query(int u, int v, int p, int fp, int k, int L, int R){
		if(L == R){
			return L;
		}
		else{
			int mid = L + R >> 1;
			int cnt = tr[tr[u].s[0]].cnt + tr[tr[v].s[0]].cnt - tr[tr[p].s[0]].cnt - tr[tr[fp].s[0]].cnt;
			if(cnt >= k) return query(tr[u].s[0], tr[v].s[0], tr[p].s[0], tr[fp].s[0], k, L, mid);
			else return query(tr[u].s[1], tr[v].s[1], tr[p].s[1], tr[fp].s[1], k - cnt, mid + 1, R);
		}
	}
	
public:
	pseg(int n){
		tr.resize(n * 25);
		root.resize(n);
		L = 1, R = n;
		clear();
	}
	
	void clear(){
		tr[0].init(), sz = 0, root[0] = malloc();
	}
	
	void copy(int v, int old){
		root[v] = root[old];
	}
	
	void modify(int v, int x, int k){
		root[v] = modify(root[v], x, k, L, R);
	}
	
	int query(int u, int v, int k){
		int p = lca(u, v), fp = fa[p][0];
		return query(root[u], root[v], root[p], root[fp], k, L, R);
	}
};

pseg tr(N);

vector<int> nums;
int f(int x){
	return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u){
	tr.copy(u, fa[u][0]);
	tr.modify(u, f(a[u]), 1);
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i];
		if(j == fa[u][0]) continue;
		dep[j] = dep[u] + 1;
		fa[j][0] = u;
		for(int k = 1; k < K; k++){
			fa[j][k] = fa[fa[j][k - 1]][k - 1];
		}
		dfs(j);
	}
}

int lca(int u, int v){
	if(dep[u] > dep[v]) swap(u, v);
	for(int k = K - 1; k >= 0; k--){
		if(dep[u] <= dep[fa[v][k]]){
			v = fa[v][k];
		}
	}
	if(u == v) return u;
	for(int k = K - 1; k >= 0; k--){
		if(fa[u][k] != fa[v][k]){
			u = fa[u][k], v = fa[v][k];
		}
	}
	return fa[u][0];
}

void solve(){
	cin >> n >> m;
	nums.pb(-inf);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		nums.pb(a[i]);
	}
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	
	memset(h, -1, sizeof(int) * (n + 1));
	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		add(a, b), add(b, a);
	}
	
	dep[1] = 1;
	dfs(1);
	int last = 0;
	while(m--){
		int u, v, k; cin >> u >> v >> k;
		u ^= last;
		last = nums[tr.query(u, v, k)];
		cout << last << '\n';
	}
}

线段树分裂与合并

  • $0,p,x,y$ ：$p$ 集合中大于等于 $x$ 且小于等于 $y$ 的数移动到新的可重集中
  • $1,p,t$ ：$t$ 集合合并到 $p$ 集合，并清空 $t$
  • $2,p,x,q$ ：$p$ 集合中加入 $x$ 个数字 $q$
  • $3,p,x,y$ ：查询 $p$ 集合中 $e\in [x,y]$ 的个数
  • $4,p,k$ ：查询 $p$ 集合中第 $k$ 小的数字，不存在则输出 $-1$
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
class segs{
private:
	struct node{
		int s[2];
		int sz;
		void init(){
			s[0] = s[1] = 0;
			sz = 0;
		}
	};
	
	int L, R, root_ord;
	vector<node> tr;
	vector<int> root, pool;
	int tt;
	
	int malloc(){
		int u = pool[tt--];
		tr[u].init();
		return u;
	}
	
	void free(int u){
		pool[++tt] = u;
	}
	
	void pu(int u){
		tr[u].sz = tr[tr[u].s[0]].sz + tr[tr[u].s[1]].sz;
	}
	
	void modify(int &u, int x, int k, int L, int R){
		if(!u) u = malloc();
		if(L == R){
			tr[u].sz += k;
			return;
		}
		int mid = L + R >> 1;
		if(x <= mid) modify(tr[u].s[0], x, k, L, mid);
		else modify(tr[u].s[1], x, k, mid + 1, R);
		pu(u);
	}
	
	int query(int u, int l, int r, int L, int R){
		if(l <= L && R <= r){
			return tr[u].sz;
		}
		else{
			int mid = L + R >> 1;
			int res = 0;
			if(l <= mid) res += query(tr[u].s[0], l, r, L, mid);
			if(r > mid) res += query(tr[u].s[1], l, r, mid + 1, R);
			return res;
		}
	}
	
	int at(int u, int k, int L, int R){
		if(L == R) return L;
		int mid = L + R >> 1;
		if(tr[tr[u].s[0]].sz >= k) return at(tr[u].s[0], k, L, mid);
		else return at(tr[u].s[1], k - tr[tr[u].s[0]].sz, mid + 1, R);
	}
	
	int merge_t(int x, int y){
		if(x == 0 || y == 0) return x + y;
		tr[x].sz += tr[y].sz;
		tr[x].s[0] = merge_t(tr[x].s[0], tr[y].s[0]);
		tr[x].s[1] = merge_t(tr[x].s[1], tr[y].s[1]);
		free(y);
		return x;
	}
	
	void split_t(int x, int &y, int k){
		if(x == 0) return;
		y = malloc();
		int sz = tr[tr[x].s[0]].sz;
		if(k > sz){
			split_t(tr[x].s[1], tr[y].s[1], k - sz);
		}
		else if(k == sz){
			swap(tr[x].s[1], tr[y].s[1]);
		}
		else{
			swap(tr[x].s[1], tr[y].s[1]);
			split_t(tr[x].s[0], tr[y].s[0], k);
		}
		tr[y].sz = tr[x].sz - k;
		tr[x].sz = k;
		return;
	}
	
public:
	segs(int n){
		L = 1, R = n;
		n <<= 3;
		tr.resize(n), root.resize(n), pool.resize(n);
		for(int i = 0; i < n; i++){
			pool[i] = i;
		}
		tt = n - 1;
		tr[0].init();
		root_ord = 1;
	}
	
	void modify(int u, int x, int k){
		modify(root[u], x, k, L, R);
	}
	
	int query(int u, int l, int r){
		return query(root[u], l, r, L, R);
	}
	
	int at(int u, int k){
		return at(root[u], k, L, R);
	}
	
	void merge(int x, int y){
		root[x] = merge_t(root[x], root[y]);
	}
	
	void split(int u, int l, int r){
		int k1 = query(root[u], 1, r, L, R);
		int k2 = query(root[u], l, r, L, R);
		int t = 0;
		split_t(root[u], root[++root_ord], k1 - k2);
		split_t(root[root_ord], t, k2);
		root[u] = merge_t(root[u], t);
	}
	
	int size(int u){
		return tr[root[u]].sz;
	}
};

int n, m;
segs tr(2e5);

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		int x; cin >> x;
		tr.modify(1, i, x);
	}
	while(m--){
		int op; cin >> op;
		if(op == 0){
			int p, x, y; cin >> p >> x >> y;
			tr.split(p, x, y);
		}
		else if(op == 1){
			int p, t; cin >> p >> t;
			tr.merge(p, t);
		}
		else if(op == 2){
			int p, x, q; cin >> p >> x >> q;
			tr.modify(p, q, x);
		}
		else if(op == 3){
			int p, x, y; cin >> p >> x >> y;
			cout << tr.query(p, x, y) << '\n';
		}
		else{
			int p, k; cin >> p >> k;
			if(tr.size(p) < k) cout << -1 << '\n';
			else cout << tr.at(p, k) << '\n';
		}
	}
}

平衡树（Splay，FHQ-Treap）

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
class splay{
private:
	struct node{
		int s[2], p, v;
		int sz;
		void init(int p_, int v_){
			s[0] = s[1] = 0, p = p_, v = v_;
			sz = 1;
		}
	};
	struct pool{
		int nodes[N], tt = 0;
		pool(){
			for(int i = 1; i < N; i++) nodes[++tt] = i;
		}
		int malloc(){
			return nodes[tt--];
		}
		void free(int u){
			nodes[++tt] = u;
		}
	};

	static node tr[N];
	static pool node_pool;
	int root = 0;
	int L, R;
	int sz = 0;
	
	void pu(int u){
		node &o = tr[u], &l = tr[o.s[0]], &r = tr[o.s[1]];
		o.sz = l.sz + r.sz + 1;
	}
	
	void rotate(int x){
		int y = tr[x].p, z = tr[y].p;
		int k = tr[y].s[1] == x;
		tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
		tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
		tr[x].s[k ^ 1] = y, tr[y].p = x;
		pu(y), pu(x);
	}
	
	void sp(int x, int k){
		while(tr[x].p != k){
			int y = tr[x].p, z = tr[y].p;
			if(z != k){
				if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
				else rotate(y);
			}
			rotate(x);
		}
		if(!k) root = x;
	}
	
	int get_k(int k){
		int u = root;
		while(u){
			if(tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
			else if(tr[tr[u].s[0]].sz + 1 == k) return u;
			else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
		}
		return -1;
	}
	
	int malloc(){
		sz++;
		return node_pool.malloc();
	}
	
	void free(int u){
		sz--;
		node_pool.free(u);
	}
	
	void recall(int u){
		if(tr[u].s[0]) recall(tr[u].s[0]);
		if(tr[u].s[1]) recall(tr[u].s[1]);
		free(u);
	}
	
public:
	splay(){
		L = insert(-inf), R = insert(inf);
	}
	
	~splay(){
		if(size()) erase(1, size());
		node_pool.free(L), node_pool.free(R);
	}
	
	int insert(int v){
		int u = root, p = 0;
		while (u) p = u, u = tr[u].s[v > tr[u].v];
		u = malloc();
		if (p) tr[p].s[v > tr[p].v] = u;
		tr[u].init(p, v);
		sp(u, 0);
		return u;
	}
	
	void erase(int lft, int rgt){
		int l = get_k(lft), r = get_k(rgt + 2);
		sp(l, 0), sp(r, l);
		recall(tr[r].s[0]);
		tr[r].s[0] = 0;
		pu(r), pu(l);
	}
	
	void erase(int v) {		//要保证v存在
		int pos = get_lower_at(v);
		erase(pos, pos);
	}
	
	int get_lower_at(int v){
		int u = root, res = 0, p = root;
		while (u)
		{
			p = u;
			if (tr[u].v >= v) u = tr[u].s[0];
			else res += tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
		}
		sp(p, 0);
		return res;
	}
	
	int get_upper_at(int v){
		return get_lower_at(v + 1);
	}
	
	int count(int v){
		return get_upper_at(v) - get_lower_at(v);
	}
	
	int at(int x){
		int t = get_k(x + 1);
		int res = tr[t].v;
		sp(t, 0);
		return res;
	}
	
	int size(){
		return sz - 2;
	}
	
	void clear(){
		if(size()) erase(1, size());
	}
};
splay::node splay::tr[N];
splay::pool splay::node_pool;

FHQ-Treap

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
class fhq_treap{
private:
	struct node{
		int s[2], k, v;
		int sz;
		
		void init(int k_){
			s[0] = s[1] = 0;
			k = k_, v = rand();
			sz = 1;
		}
	};
	struct pool{
		int nodes[N], tt = 0;
		pool(){
			for(int i = 1; i < N; i++) nodes[++tt] = i;
		}
		int malloc(){
			return nodes[tt--];
		}
		void free(int u){
			nodes[++tt] = u;
		}
	};
	int root = 0, sz = 0;
	static node tr[N];
	static pool node_pool;
	
	void pu(int u){
		node &o = tr[u], &l = tr[tr[u].s[0]], &r = tr[tr[u].s[1]];
		o.sz = l.sz + r.sz + 1;
	}
	
	pii split(int u, int k){
		if(!u) return {0, 0};
		if(tr[u].k < k){
			pii t = split(tr[u].s[1], k);
			tr[u].s[1] = t.first;
			pu(u);
			return {u, t.second};
		}
		else{
			pii t = split(tr[u].s[0], k);
			tr[u].s[0] = t.second;
			pu(u);
			return {t.first, u};
		}
	}
	
	int merge(int u, int v){
		if(!u || !v) return u + v;
		if(tr[u].v < tr[v].v){
			tr[u].s[1] = merge(tr[u].s[1], v);
			pu(u);
			return u;
		}
		else{
			tr[v].s[0] = merge(u, tr[v].s[0]);
			pu(v);
			return v;
		}
	}
	
	int malloc(){
		sz++;
		return node_pool.malloc();
	}
	
	void free(int u){
		sz--;
		node_pool.free(u);
	}
	
	void recall(int u){
		if(!u) return;
		recall(tr[u].s[0]);
		recall(tr[u].s[1]);
		free(u);
	}
	
public:
	~fhq_treap(){
		recall(root);
	}
	
	void insert(int k){
		int u = malloc();
		tr[u].init(k);
		pii t = split(root, k);
		root = merge(merge(t.first, u), t.second);
	}
	
	void erase(int k){
		pii x = split(root, k);
		pii y = split(x.second, k + 1);
		int u = y.first;
		free(u);
		y.first = merge(tr[u].s[0], tr[u].s[1]);
		root = merge(x.first, merge(y.first, y.second));
	}
	
	int get_lower_at(int k){
		int res = 0;
		pii t = split(root, k);
		res = tr[t.first].sz + 1;
		root = merge(t.first, t.second);
		return res;
	}
	
	int get_upper_at(int k){
		return get_lower_at(k + 1);
	}
	
	int at(int k){
		int u = root;
		while(u){
			if(k == tr[tr[u].s[0]].sz + 1) return tr[u].k;
			else if(k < tr[tr[u].s[0]].sz + 1) u = tr[u].s[0];
			else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
		}
	}
	
	int size(){
		return sz;
	}
};
fhq_treap::node fhq_treap::tr[N];
fhq_treap::pool fhq_treap::node_pool;

平衡树维护序列（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
class splay{
private:
	struct node{
		int s[2], p, v;
		int sz, sum, ms, ls, rs;	//sz:子树大小 sum:子树和 ms:子树最大段 ls:左起最大段 rs:右起最大段
		int rev, same;	//lazy tag  rev:翻转 same:变相同
		void init(int p_, int v_){
			s[0] = s[1] = 0, p = p_, v = v_;
			sz = 1, sum = ms = v;
			ls = rs = max(v, 0ll);
			rev = same = 0;
		}
	};
	struct pool{
		int nodes[N], tt = 0;
		pool(){
			for(int i = 1; i < N; i++) nodes[++tt] = i;
		}
		int malloc(){
			return nodes[tt--];
		}
		void free(int u){
			nodes[++tt] = u;
		}
	};
	static node tr[N];
	static pool node_pool;
	int root = 0;
	int sz = 0;
	
	void pu(int u){
		node &o = tr[u], &l = tr[o.s[0]], &r = tr[o.s[1]];
		o.sz = l.sz + r.sz + 1;
		o.sum = l.sum + r.sum + o.v;
		o.ls = max(l.ls, l.sum + o.v + r.ls);
		o.rs = max(r.rs, r.sum + o.v + l.rs);
		o.ms = max({l.ms, r.ms, l.rs + o.v + r.ls});
	}
	
	void pd(int u){
		node &o = tr[u], &l = tr[o.s[0]], &r = tr[o.s[1]];
		if(o.same){
			o.same = o.rev = 0;
			if(o.s[0]) l.same = true, l.v = o.v, l.sum = l.v * l.sz;
			if(o.s[1]) r.same = true, r.v = o.v, r.sum = r.v * r.sz;
			if(o.v > 0){
				if(o.s[0]) l.ms = l.ls = l.rs = l.sum;
				if(o.s[1]) r.ms = r.ls = r.rs = r.sum;
			}
			else{
				if(o.s[0]) l.ms = l.v, l.ls = l.rs = 0;
				if(o.s[1]) r.ms = r.v, r.ls = r.rs = 0;
			}
		}
		else if(o.rev){
			o.rev = 0, l.rev ^= 1, r.rev ^= 1;
			swap(l.ls, l.rs), swap(r.ls, r.rs);
			swap(l.s[0], l.s[1]), swap(r.s[0], r.s[1]);
		}
	}
	
	void rotate(int x){
		int y = tr[x].p, z = tr[y].p;
		int k = tr[y].s[1] == x;
		tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
		tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
		tr[x].s[k ^ 1] = y, tr[y].p = x;
		pu(y), pu(x);
	}
	
	void sp(int x, int k){
		while(tr[x].p != k){
			int y = tr[x].p, z = tr[y].p;
			if(z != k){
				if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
				else rotate(y);
			}
			rotate(x);
		}
		if(!k) root = x;
	}
	
	int build(int p, int l, int r, int *w){
		int mid = l + r >> 1;
		int u = malloc();
		tr[u].init(p, w[mid]);
		if(l < mid) tr[u].s[0] = build(u, l, mid - 1, w);
		if(r > mid) tr[u].s[1] = build(u, mid + 1, r, w);
		pu(u);
		return u;
	}
	
	int get_k(int k){
		int u = root;
		while(u){
			pd(u);
			if(tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
			else if(tr[tr[u].s[0]].sz + 1 == k) return u;
			else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
		}
		return -1;
	}
	
	int malloc(){
		sz++;
		return node_pool.malloc();
	}
	
	void free(int u){
		sz--;
		node_pool.free(u);
	}
	
	void recall(int u){
		if(tr[u].s[0]) recall(tr[u].s[0]);
		if(tr[u].s[1]) recall(tr[u].s[1]);
		free(u);
	}
	
public:
	splay(){
		tr[0].ms = -inf;
		int w[2] = {-inf, -inf};
		root = build(0, 0, 1, w);
	}
	
	~splay(){
		if(size()) erase(1, size());
	}
	
	void insert(int k, int *w, int cnt){
		int l = get_k(k), r = get_k(k + 1);
		sp(l, 0), sp(r, l);
		int u = build(r, 1, cnt, w);
		tr[r].s[0] = u;
		pu(r), pu(l);
	}
	
	void erase(int lft, int rgt){
		int l = get_k(lft), r = get_k(rgt + 2);
		sp(l, 0), sp(r, l);
		recall(tr[r].s[0]);
		tr[r].s[0] = 0;
		pu(r), pu(l);
	}
	
	void modify(int lft, int rgt, int c){
		int l = get_k(lft), r = get_k(rgt + 2);
		sp(l, 0), sp(r, l);
		node &s = tr[tr[r].s[0]];
		s.same = 1, s.v = c, s.sum = c * s.sz;
		if(c > 0) s.ms = s.ls = s.rs = s.sum;
		else s.ms = c, s.ls = s.rs = 0;
		pu(r), pu(l);
	}
	
	void reverse(int lft, int rgt){
		int l = get_k(lft), r = get_k(rgt + 2);
		sp(l, 0), sp(r, l);
		node &s = tr[tr[r].s[0]];
		s.rev ^= 1;
		swap(s.ls, s.rs);
		swap(s.s[0], s.s[1]);
		pu(r), pu(l);
	}
	
	int query(int lft, int rgt){
		int l = get_k(lft), r = get_k(rgt + 2);
		sp(l, 0), sp(r, l);
		return tr[tr[r].s[0]].sum;
	}
	
	int query_max_seg(){
		return tr[root].ms;
	}
	
	int at(int x){
		int t = get_k(x + 1);
		int res = tr[t].v;
		sp(t, 0);
		return res;
	}
	
	int size(){
		return sz - 2;
	}
	
	void clear(){
		if(size()) erase(1, size());
	}
};
splay::node splay::tr[N];
splay::pool splay::node_pool;

int n, m;
int w[N], t[N];

void solve(){
	cin >> n >> m;
	splay tr;
	for(int i = 1; i <= n; i++){
		cin >> w[i];
	}
	tr.insert(1, w, n);
	
	while(m--){
		string op; cin >> op;
		if(op == "INSERT"){
			int p, cnt; cin >> p >> cnt;
			for(int i = 1; i <= cnt; i++) cin >> t[i];
			tr.insert(p + 1, t, cnt);
		}
		else if(op == "DELETE"){
			int p, cnt; cin >> p >> cnt;
			tr.erase(p, p + cnt - 1);
		}
		else if(op == "MAKE-SAME"){
			int p, cnt, c; cin >> p >> cnt >> c;
			tr.modify(p, p + cnt - 1, c);
		}
		else if(op == "REVERSE"){
			int p, cnt; cin >> p >> cnt;
			tr.reverse(p, p + cnt - 1);
		}
		else if(op == "GET-SUM"){
			int p, cnt; cin >> p >> cnt;
			cout << tr.query(p, p + cnt - 1) << '\n';
		}
		else if(op == "MAX-SUM"){
			cout << tr.query_max_seg() << '\n';
		}
	}
}

可持久化平衡树

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
class pfhq_treap{
private:
	struct node{
		int s[2], k, v;
		int sz;
		
		void init(int k_){
			s[0] = s[1] = 0;
			k = k_, v = rand();
			sz = 1;
		}
	};
	vector<node> tr;
	vector<int> root, pool;
	int tt;
	
	int malloc(){
		int u = pool[tt--];
		tr[u] = {{0, 0}, 0, 0, 0};
		return u;
	}
	
	void free(int u){
		pool[++tt] = u;
	}
	
	void pu(int u){
		node &o = tr[u], &l = tr[tr[u].s[0]], &r = tr[tr[u].s[1]];
		o.sz = l.sz + r.sz + 1;
	}
	
	pii split(int u, int k){
		if(!u) return {0, 0};
		int nu = malloc();
		tr[nu] = tr[u];
		if(tr[u].k < k){
			pii t = split(tr[nu].s[1], k);
			tr[nu].s[1] = t.first;
			pu(nu);
			return {nu, t.second};
		}
		else{
			pii t = split(tr[nu].s[0], k);
			tr[nu].s[0] = t.second;
			pu(nu);
			return {t.first, nu};
		}
	}
	
	int merge(int u, int v){
		if(!u || !v) return u + v;
		if(tr[u].v < tr[v].v){
			int nu = malloc();
			tr[nu] = tr[u];
			tr[nu].s[1] = merge(tr[nu].s[1], v);
			pu(nu);
			return nu;
		}
		else{
			int nv = malloc();
			tr[nv] = tr[v];
			tr[nv].s[0] = merge(u, tr[nv].s[0]);
			pu(nv);
			return nv;
		}
	}
	
public:
	pfhq_treap(int n){
		n *= 50;
		tr.resize(n), root.resize(n), pool.resize(n);
		for(int i = 0; i < n; i++) pool[i] = i;
		tt = n - 1;
		tr[0] = {0, 0, 0, 0, 0};
	}
	
	void copy(int v, int old){
		root[v] = root[old];
	}
	
	void insert(int v, int k){
		int u = malloc();
		tr[u].init(k);
		pii t = split(root[v], k);
		root[v] = merge(merge(t.first, u), t.second);
	}
	
	void erase(int v, int k){
		pii x = split(root[v], k);
		pii y = split(x.second, k + 1);
		int u = y.first;
		free(u);
		y.first = merge(tr[u].s[0], tr[u].s[1]);
		root[v] = merge(x.first, merge(y.first, y.second));
	}
	
	int get_lower_at(int v, int k){
		int res = 0;
		pii t = split(root[v], k);
		res = tr[t.first].sz + 1;
		root[v] = merge(t.first, t.second);
		return res;
	}
	
	int get_upper_at(int v, int k){
		return get_lower_at(v, k + 1);
	}
	
	int at(int v, int k){
		int u = root[v];
		while(u){
			if(k == tr[tr[u].s[0]].sz + 1) return tr[u].k;
			else if(k < tr[tr[u].s[0]].sz + 1) u = tr[u].s[0];
			else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
		}
	}
};

const int inf = 1 << 31;

void solve(){
	int n; cin >> n;
	pfhq_treap tr(n);
	tr.insert(0, -inf + 1);
	tr.insert(0, inf - 1);
	for(int i = 1; i <= n; i++){
		int v, op, x;
		cin >> v >> op >> x;
		tr.copy(i, v);
		if(op == 1){
			tr.insert(i, x);
		}
		else if(op == 2){
			if(tr.at(i, tr.get_lower_at(i, x)) == x){
				tr.erase(i, x);
			}
		}
		else if(op == 3){
			cout << tr.get_lower_at(i, x) - 1 << '\n';
		}
		else if(op == 4){
			cout << tr.at(i, x + 1) << '\n';
		}
		else if(op == 5){
			cout << tr.at(i, tr.get_lower_at(i, x) - 1) << '\n';
		}
		else{
			cout << tr.at(i, tr.get_upper_at(i, x)) << '\n';
		}
	}
}

LCT

  • $0,x,y$ ：$a[x]\oplus \dots \oplus a[y]$
  • $1,x,y$ ：若 $x$ 与 $y$ 不连通，$link(x,y)$
  • $2,x,y$ ：若 $x$ 与 $y$ 有连边，则 $cut(x,y)$
  • $3,x,y$ ：$a[x]=y$
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
class lct{
	struct node{
		int s[2], p, v;
		int sum, rev;
		node(){
			s[0] = s[1] = 0, p = v = 0;
			sum = rev = 0;
		}
	};
	vector<node> tr;
	vector<int> stk;
	
	void pu(int x){
		tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
	}
	
	void pdrev(int x){
		swap(tr[x].s[0], tr[x].s[1]);
		tr[x].rev ^= 1;
	}
	
	void pd(int x){
		if(tr[x].rev){
			pdrev(tr[x].s[0]), pdrev(tr[x].s[1]);
			tr[x].rev = 0;
		}
	}
	
	bool isroot(int x){
		return tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x;
	}
	
	void rotate(int x){
		int y = tr[x].p, z = tr[y].p;
		int k = tr[y].s[1] == x;
		if (!isroot(y)) tr[z].s[tr[z].s[1] == y] = x;
		tr[x].p = z;
		tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
		tr[x].s[k ^ 1] = y, tr[y].p = x;
		pu(y), pu(x);
	}
	
	void splay(int x){
		int top = 0, r = x;
		stk[ ++ top] = r;
		while(!isroot(r)) stk[++top] = r = tr[r].p;
		while(top) pd(stk[top--]);
		while(!isroot(x)){
			int y = tr[x].p, z = tr[y].p;
			if (!isroot(y)){
				if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
				else rotate(y);
			}
			rotate(x);
		}
	}
	
	void access(int x){  // 建立一条从根到x的路径，同时将x变成splay的根节点
		int z = x;
		for(int y = 0; x; y = x, x = tr[x].p){
			splay(x);
			tr[x].s[1] = y, pu(x);
		}
		splay(z);
	}
	
	void makeroot(int x){  // 将x变成原树的根节点
		access(x), pdrev(x);
	}
	
	int findroot(int x){  // 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点
		access(x);
		while(tr[x].s[0]) pd(x), x = tr[x].s[0];
		splay(x);
		return x;
	}
	
	void split(int x, int y){  // 给x和y之间的路径建立一个splay，其根节点是y
		makeroot(x);
		access(y);
	}
	
public:
	lct(int n){
		tr.resize(n + 1);
		stk.resize(n + 1);
	}
	
	void link(int x, int y){  // 如果x和y不连通，则加入一条x和y之间的边
		makeroot(x);
		if(findroot(y) != x) tr[x].p = y;
	}
	
	void cut(int x, int y){  // 如果x和y之间存在边，则删除该边
		makeroot(x);
		if(findroot(y) == x && tr[y].p == x && !tr[y].s[0]){
			tr[x].s[1] = tr[y].p = 0;
			pu(x);
		}
	}
	
	int query(int x, int y){
		split(x, y);
		return tr[y].sum;
	}
	
	void modify(int x, int k){
		splay(x);
		tr[x].v = k;
		pu(x);
	}
};

void solve(){
	int n, m; cin >> n >> m;
	lct tr(n);
	for(int i = 1; i <= n; i++){
		int k; cin >> k;
		tr.modify(i, k);
	}
	while(m--){
		int op, x, y; cin >> op >> x >> y;
		if(op == 0) cout << tr.query(x, y) << '\n';
		else if(op == 1) tr.link(x, y);
		else if(op == 2) tr.cut(x, y);
		else tr.modify(x, y);
	}
}

树套树

  • $1,l,r,k$ ：查询 $k$ 在区间内的排名
  • $2,l,r,k$ ：查询在区间内排名为 $k$ 的值
  • $3,x,k$ ：$a[x] = k$
  • $4,l,r,k$ ：查询 $k$ 在区间内的前驱
  • $5,l,r,k$ ：查询 $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
int n, m;

namespace Splay{
	struct Node{
		int s[2], p;
		int v, size;
		void init(int p_, int v_){
			p = p_, v = v_, size = 1;
		}
	}tr[N];
	
	int idx;
	
	void pushup(int x){
		tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
	}
	
	void rotate(int x){
		int y = tr[x].p, z = tr[y].p;
		int k = tr[y].s[1] == x;
		tr[z].s[tr[z].s[1]==y] = x, tr[x].p = z;
		tr[y].s[k] = tr[x].s[k^1], tr[tr[x].s[k^1]].p = y;
		tr[x].s[k^1] = y, tr[y].p = x;
		pushup(y), pushup(x);
	}
	
	void splay(int& root, int x, int k){
		while(tr[x].p!=k){
			int y = tr[x].p, z = tr[y].p;
			if(z!=k){
				if((tr[y].s[1]==x)^(tr[z].s[1]==y)) rotate(x);
				else rotate(y);
			}
			rotate(x);
		}
		if(!k) root = x;
	}
	
	void insert(int& root, int v){
		int u = root, p = 0;
		while(u) p = u, u = tr[u].s[v>tr[u].v];
		u = ++idx;
		if(p) tr[p].s[v>tr[p].v] = u;
		tr[u].init(p, v);
		splay(root, u, 0);
	}
	
	int get_k(int root, int v){
		int u = root, res = 0;
		while(u){
			if(tr[u].v>=v) u = tr[u].s[0];
			else res+=tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
		}
		return res;
	}
	
	int find(int root, int v){
		int u = root;
		while(u){
			if(v > tr[u].v) u = tr[u].s[1];
			else if(v < tr[u].v) u = tr[u].s[0];
			else break;
		}
		return u;
	}
	
	void modify(int& root, int x, int y){
		int u = find(root, x);
		splay(root, u, 0);
		int l = tr[u].s[0], r = tr[u].s[1];
		while(tr[l].s[1]) l = tr[l].s[1];
		while(tr[r].s[0]) r = tr[r].s[0];
		splay(root, l, 0), splay(root, r, l);
		tr[r].s[0] = 0;
		pushup(r), pushup(l);
		insert(root, y);
	}
	
	int get_pre(int root, int v){
		int u = root, res = -INF;
		while(u){
			if(tr[u].v<v) res = max(res, tr[u].v), u = tr[u].s[1];
			else u = tr[u].s[0];
		}
		return res;
	}
	
	int get_suc(int root, int v){
		int u = root, res = INF;
		while(u){
			if(tr[u].v>v) res = min(res, tr[u].v), u = tr[u].s[0];
			else u = tr[u].s[1];
		}
		return res;
	}
}

namespace Segment{
	using Splay::insert;
	
	struct Node{
		int l, r, root;
	}tr[N];
	int w[N];
	
	void build(int u, int l, int r){
		tr[u] = {l, r};
		insert(tr[u].root, -INF);
		insert(tr[u].root, INF);
		for(int i = l; i<=r; i++) insert(tr[u].root, w[i]);
		if(l == r) return;
		int mid = l + r >> 1;
		build(u<<1, l, mid);
		build(u<<1|1, mid+1, r);
	}
	
	int query(int u, int l, int r, int x){
		if(l<=tr[u].l && tr[u].r<=r) return Splay::get_k(tr[u].root, x) - 1;
		int mid = tr[u].l + tr[u].r >> 1, res = 0;
		if(l<=mid) res += query(u<<1, l, r, x);
		if(r>mid) res += query(u<<1|1, l, r, x);
		return res;
	}
	
	void modify(int u, int p, int x){
		Splay::modify(tr[u].root, w[p], x);
		if(tr[u].l == tr[u].r) return;
		int mid = tr[u].l + tr[u].r >> 1;
		if(p<=mid) modify(u<<1, p, x);
		else modify(u<<1|1, p, x);
	}
	
	int query_pre(int u, int l, int r, int x){
		if(l<=tr[u].l && tr[u].r<=r) return Splay::get_pre(tr[u].root, x);
		int mid = tr[u].l + tr[u].r >> 1, res = -INF;
		if(l<=mid) res = max(res, query_pre(u<<1, l, r, x));
		if(r>mid) res = max(res, query_pre(u<<1|1, l, r, x));
		return res;
	}
	
	int query_sub(int u, int l, int r, int x){
		if(l<=tr[u].l && tr[u].r<=r) return Splay::get_suc(tr[u].root, x);
		int mid = tr[u].l + tr[u].r >> 1, res = INF;
		if(l<=mid) res = min(res, query_sub(u<<1, l, r, x));
		if(r>mid) res = min(res, query_sub(u<<1|1, l, r, x));
		return res;
	}
}

signed main(){
	IOS using namespace Segment;
	cin>>n>>m;
	for(int i = 1; i <= n; i++) cin>>w[i];
	build(1, 1, n);
	while(m--){
		int op, l, r, x;
		cin>>op;
		if(op == 1){
			cin>>l>>r>>x;
			cout<<query(1, l, r, x)+1<<'\n';
		}
		else if(op == 2){
			cin>>l>>r>>x;
			int ll = 0, rr = 1e8;
			while(ll<rr){
				int mid = ll + rr + 1 >> 1;
				if(query(1, l, r, mid) + 1 <= x) ll = mid;
				else rr = mid - 1;
			}
			cout<<rr<<'\n';
		}
		else if(op == 3){
			cin>>l>>x;
			modify(1, l, x);
			w[l] = x;
		}
		else if(op == 4){
			cin>>l>>r>>x;
			cout<<query_pre(1, l, r, x)<<'\n';
		}
		else{
			cin>>l>>r>>x;
			cout<<query_sub(1, l, r, x)<<'\n';
		}
	}
}

ST表

  • $l,r$ ：$max(a[l,r])$
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
struct rmq{
	int f[N][M];
	void init(int *w, int n){
		for (int j = 0; j < M; j ++ )
			for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
				if (!j) f[i][j] = w[i];
				else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
	}
	int query(int l, int r){
		int len = r - l + 1;
		int k = log(len) / log(2);
		return max(f[l][k], f[r - (1 << k) + 1][k]);
	}
};

int n, m;
int w[N];
rmq q;

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> w[i];
	q.init(w, n);
	cin >> m;
	while(m--){
		int l, r; cin >> l >> r;
		cout << q.query(l, r) << '\n';
	}
}

二维ST表

矩形区间，空间要求大

$a,b,c,d$ ：$max(a[a,c][b,d])$

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
struct rmq{
	int f[N][N][M][M];
	void init(int w[N][N], int n, int m){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				f[i][j][0][0] = w[i][j];
			}
		}
		int t = log((double)m) / log(2.0);
		for(int i = 0; i <= t; i++){
			for(int j = 0; j <= t; j++){
				if(i == 0 && j == 0) continue;
				for(int r = 1; r + (1 << i) - 1 <= n; r++){
					for(int c = 1; c + (1 << j) - 1 <= m; c++){
						if(i) f[r][c][i][j] = max(f[r][c][i - 1][j], f[r + (1 << (i - 1))][c][i - 1][j]);
						else f[r][c][i][j] = max(f[r][c][i][j - 1], f[r][c + (1 << (j - 1))][i][j - 1]);
					}
				}
			}
		}
	}
	int query(int a, int b, int c, int d){
		int k1 = log(double(c - a + 1)) / log(2.0);
		int k2 = log(double(d - b + 1)) / log(2.0);
		int m1 = f[a][b][k1][k2];
		int m2 = f[c - (1 << k1) + 1][b][k1][k2];
		int m3 = f[a][d - (1 << k2) + 1][k1][k2];
		int m4 = f[c - (1 << k1) + 1][d - (1 << k2) + 1][k1][k2];
		return max({m1, m2, m3, m4});
	}
};

正方形区间，空间要求小

  • $a,b,c,d$ ：$max(a[a,c][b,d]),c-a=d-b$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct rmq_max{
	int f[N][N][M];
	void init(int w[N][N], int n, int m){
		for(int k = 0; (1 << k) <= n; k++){
			for(int i = 1; i + (1 << k) - 1 <= n; i++){
				for(int j = 1; j + (1 << k) - 1 <= m; j++){
					if(!k) f[i][j][k] = w[i][j];
					else f[i][j][k] = max({f[i][j][k - 1], f[i][j + (1 << (k - 1))][k - 1], f[i + (1 << (k - 1))][j][k - 1], f[i + (1 << (k - 1))][j + (1 << (k - 1))][k - 1]});
				}
			}
		}
	}
	int query(int a, int b, int c, int d){
		int k = log2(double(c - a + 1));
		c = c - (1 << k) + 1, d = d - (1 << k) + 1;
		return max({f[a][b][k], f[c][b][k], f[a][d][k], f[c][d][k]});
	}
};

树链剖分

  • $1,u,v,k$ ：$tr[u,v]=tr[u,v]+k$
  • $2,u,v$ ：$\sum tr[u,v]$
  • $3,u,k$ ：$sub_tr[u]=sub_tr[u]+k$
  • $4,u$ ：$\sum sub_tr[u]$
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
class seg;	//区间加，区间求和线段树

struct tree{
	int h[N], e[M], ne[M], idx;
	int id[N], cnt;
	int dep[N], sz[N], top[N], fa[N], son[N];
	
	seg tr(N);
	
	void add(int a, int b){
		e[idx] = b, ne[idx] = h[a], h[a] = idx++;
	}
	
	void dfs1(int u, int father, int depth){
		dep[u] = depth, sz[u] = 1, fa[u] = father;
		for(int i = h[u]; ~i; i = ne[i]){
			int j = e[i];
			if(j == father) continue;
			dfs1(j, u, depth+1);
			sz[u] += sz[j];
			if(sz[j] > sz[son[u]]) son[u] = j;
		}
	}
	
	void dfs2(int u, int tp){
		id[u] = ++cnt, top[u] = tp;
		if(son[u]) dfs2(son[u], tp);
		for(int i = h[u]; ~i; i = ne[i]){
			int j = e[i];
			if(j == fa[u] || j == son[u]) continue;
			dfs2(j, j);
		}
	}
	
	void init(int n){
		memset(h, -1, sizeof(int) * (n + 1));
		idx = cnt = 0;
		memset(son, 0, sizeof(int) * (n + 1));
		tr.build(1, 1, n);
	}
	
	void build(int root, int n){
		dfs1(root, -1, 1);
		dfs2(root, root);
	}
	
	void modify(int u, int v, int k){
		while(top[u] != top[v]){
			if(dep[top[u]] < dep[top[v]]) swap(u, v);
			tr.modify(1, id[top[u]], id[u], k);
			u = fa[top[u]];
		}
		if(dep[u] < dep[v]) swap(u, v);
		tr.modify(1, id[v], id[u], k);
	}
	
	void modify(int u, int k){
		tr.modify(1, id[u], id[u] + sz[u] - 1, k);
	}
	
	seg::node query(int u, int v){
		seg::node res = {0, 0, 0, 0};
		while(top[u] != top[v]){
			if(dep[top[u]] < dep[top[v]]) swap(u, v);
			res = res + tr.query(1, id[top[u]], id[u]);
			u = fa[top[u]];
		}
		if(dep[u] < dep[v]) swap(u, v);
		res = res + tr.query(1, id[v], id[u]);
		return res;
	}
	
	seg::node query(int u){
		return tr.query(1, id[u], id[u] + sz[u] - 1);
	}
};

int n, m, r, p;
int w[N];
tree tr;

void solve(){
	cin >> n >> m >> r >> p;
	for(int i = 1; i <= n; i++) cin >> w[i];
	tr.init(n);
	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		tr.add(a, b), tr.add(b, a);
	}
	tr.build(r, n);
	for(int i = 1; i <= n; i++) tr.modify(i, i, w[i]);
	while(m--){
		int op; cin >> op;
		if(op == 1){
			int u, v, k; cin >> u >> v >> k;
			tr.modify(u, v, k);
		}
		else if(op == 2){
			int u, v; cin >> u >> v;
			cout << tr.query(u, v).sum % p << '\n';
		}
		else if(op == 3){
			int u, k; cin >> u >> k;
			tr.modify(u, k);
		}
		else{
			int u; cin >> u;
			cout << tr.query(u).sum % p << '\n';
		}
	}
}

可并堆

  • $1,x,y$ ：将第 $x$ 个数和第 $y$ 个数所在的小根堆合并
  • $2,x$ ：输出第 $x$ 个数所在的堆的堆顶，并删除堆顶元素
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
class mheap{
private:
	struct node{
		int s[2];
		int dist;
		pii w;
		void init(pii w_ = {0, 0}){
			s[0] = s[1] = 0;
			w = w_, dist = 0;
		}
	};
	
	vector<node> tr;
	vector<int> root;
	int sz;
	
	vector<char> st;
	
	int malloc(){
		int u = ++sz;
		tr[u].init();
		return u;
	}
	
	int merge_t(int x, int y){
		if(x == 0 || y == 0) return x + y;
		if(tr[x].w > tr[y].w) swap(x, y);
		tr[x].s[1] = merge_t(tr[x].s[1], y);
		if(tr[tr[x].s[0]].dist < tr[tr[x].s[1]].dist) swap(tr[x].s[0], tr[x].s[1]);
		tr[x].dist = tr[tr[x].s[1]].dist + 1;
		return x;
	}
	
	int find(int x){
		if(root[x] != x) root[x] = find(root[x]);
		return root[x];
	}
	
public:
	mheap(int n){
		tr.resize(n + 1);
		root.resize(n + 1);
		st.resize(n + 1);
		clear();
	}
	
	void clear(){
		fill(st.begin(), st.end(), '0');
		tr[0].dist = -1, sz = 0;
	}
	
	void insert(pii w){
		int u = malloc();
		tr[u].w = w;
		root[u] = u;
	}
	
	void merge(int x, int y){
		if(st[x] == '1' || st[y] == '1') return;
		x = find(x), y = find(y);
		if(x != y) root[x] = root[y] = merge_t(x, y);
	}
	
	int query(int x){
		if(st[x] == '1') return -1;
		x = find(x);
		return tr[x].w.first;
	}
	
	void pop(int x){
		x = find(x);
		st[x] = '1';
		root[tr[x].s[0]] = root[tr[x].s[1]] = root[x] = merge_t(tr[x].s[0], tr[x].s[1]);
		tr[x].init();
	}
};

void solve(){
	int n, m; cin >> n >> m;
	mheap h(n);
	for(int i = 1; i <= n; i++){
		int w; cin >> w;
		h.insert({w, i});
	}
	while(m--){
		int op; cin >> op;
		if(op == 1){
			int x, y; cin >> x >> y;
			h.merge(x, y);
		}
		else{
			int x; cin >> x;
			int res = h.query(x);
			cout << res << '\n';
			if(res != -1) h.pop(x);
		}
	}
}

可持久化可并堆

  • $1,v,x$ ：$S_i = S_v \cup {x}$
  • $2,u,v$ ：$S_i = S_u \cup S_v$
  • $3,v$ ：$S_i = S_v$ ，$Pop(S_i)$
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
class pmheap{
private:
	struct node{
		int s[2];
		int dist;
		int w;
		void init(int w_ = 0){
			s[0] = s[1] = 0;
			w = w_, dist = 0;
		}
	};
	
	vector<node> tr;
	vector<int> root;
	int sz;
	
	int malloc(){
		int u = ++sz;
		tr[u].init();
		return u;
	}
	
	int merge_t(int x, int y){
		if(x == 0 || y == 0) return x + y;
		if(tr[x].w > tr[y].w) swap(x, y);
		int u = malloc();
		tr[u] = tr[x];
		tr[u].s[1] = merge_t(tr[u].s[1], y);
		if(tr[tr[u].s[0]].dist < tr[tr[u].s[1]].dist) swap(tr[u].s[0], tr[u].s[1]);
		tr[u].dist = tr[tr[u].s[1]].dist + 1;
		return u;
	}
	
public:
	pmheap(int n){
		tr.resize(n * 30);
		root.resize(n * 5);
		clear();
	}
	
	void clear(){
		tr[0].init(), tr[0].dist = -1, sz = 0, root[0] = 0;
	}
	
	void copy(int v, int old){
		root[v] = root[old];
	}
	
	void create(int v, int w){
		int u = malloc();
		tr[u].init(w);
		root[v] = u;
	}
	
	void merge(int x, int y){
		root[x] = merge_t(root[x], root[y]);
	}
	
	int query(int x){
		x = root[x];
		if(x == 0) return -1;
		return tr[x].w;
	}
	
	void pop(int x){
		root[x] = merge_t(tr[root[x]].s[0], tr[root[x]].s[1]);
	}
};

void solve(){
	int n; cin >> n;
	pmheap h(n);
	int s = 0;
	for(int i = 1; i <= n; i++){
		int op; cin >> op;
		if(op == 1){
			int a, b; cin >> a >> b;
			int v = (a + s) % i, x = (b + 17 * s) % 1000000001;
			h.create(i, x), h.merge(i, v);
			int res = h.query(i);
			if(res == -1) cout << "empty" << '\n', res = 0;
			else cout << res << '\n';
			s = (s + res) % 239017;
		}
		else if(op == 2){
			int a, b; cin >> a >> b;
			int u = (a + s) % i, v = (b + 13 * s) % i;
			h.copy(i, u), h.merge(i, v);
			int res = h.query(i);
			if(res == -1) cout << "empty" << '\n', res = 0;
			else cout << res << '\n';
			s = (s + res) % 239017;
		}
		else{
			int a; cin >> a;
			int v = (a + s) % i;
			h.copy(i, v);
			int res = h.query(i);
			if(res == -1) cout << "empty" << '\n', res = 0;
			else cout << res << '\n', h.pop(i);
			s = (s + res) % 239017;
		}
	}
}

CDQ分治（三维偏序）

$f(i)$ ：$\sum_{j\in [1,i-1]\cup [i+1,n]} (a_i \ge a_j \and b_i \ge b_j \ge c_i \ge c_j)$

$cnt[d]$ ：$\sum_{i\in [1,n]}(f(i)=d)$

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
struct bi;	//单点修改+区间查询

using tiii = tuple<int, int, int>;

struct cdq{
	struct E{
		int a, b, c;
		int cnt;	//e的个数
		int res;	//f(i)的个数
	};
	int n;
	E es[N];
	bi tr;
	map<tiii, int> e_cnt;
	
	void init(tiii a[], int n_, int k){
		for(int i = 1; i <= n_; i++){
			e_cnt[a[i]]++;
		}
		n = 0;
		for(auto &[e, cnt] : e_cnt){
			auto [a, b, c] = e;
			es[++n] = {a, b, c, cnt, 0};
//			cout << a << ' ' << b << ' ' << c << ' ' << cnt << '\n';
		}
		tr.init(k);
	}
	
	void calc(int l, int r){
		if(l == r) return;
		int mid = l + r >> 1;
		calc(l, mid), calc(mid + 1, r);
		auto cmp_y = [](auto &lhs, auto &rhs){
			if(lhs.b != rhs.b) return lhs.b < rhs.b;
			return lhs.c < rhs.c;
		};
		sort(es + l, es + mid + 1, cmp_y);
		sort(es + mid + 1, es + r + 1, cmp_y);
		int i = l, j = mid + 1;
		while(j <= r){
			while(i <= mid && es[i].b <= es[j].b){
				tr.add(es[i].c, es[i].cnt);
				i++;
			}
			es[j].res += tr.sum(es[j].c);
			j++;
		}
		for(int t = l; t < i; t++){
			tr.add(es[t].c, -es[t].cnt);
		}
	}
	
	void run(){
		calc(1, n);
		for(int i = 1; i <= n; i++){
			es[i].res += es[i].cnt - 1;
		}
	}
};

int n, k;
tiii es[N];

cdq c;
int cnt[N];

void solve(){
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		int a, b, c; cin >> a >> b >> c;
		es[i] = {a, b, c};
	}
	c.init(es, n, k);
	c.run();
	for(int i = 1; i <= c.n; i++){
		auto &e = c.es[i];
		cnt[e.res] += e.cnt;
	}
	for(int i = 0; i < n; i++){
		cout << cnt[i] << '\n';
	}
}

树上启发式合并

给出一棵 $n$ 个节点以 $1$ 为根的树，节点 $u$ 的颜色为 $c_u$ ，现在对于每个结点 u 询问以 $u$ 为根的子树里一共出现了多少种不同的颜色。

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
const int N = 2e5 + 5;

int n;

// g[u]: 存储与 u 相邻的结点
vector<int> g[N];

// sz: 子树大小
// big: 重儿子
// col: 结点颜色
// L[u]: 结点 u 的 DFS 序
// R[u]: 结点 u 子树中结点的 DFS 序的最大值
// Node[i]: DFS 序为 i 的结点
// ans: 存答案
// cnt[i]: 颜色为 i 的结点个数
// totColor: 目前出现过的颜色个数
int sz[N], big[N], col[N], L[N], R[N], Node[N], totdfn;
int ans[N], cnt[N], totColor;

void add(int u) {
  if (cnt[col[u]] == 0) ++totColor;
  cnt[col[u]]++;
}

void del(int u) {
  cnt[col[u]]--;
  if (cnt[col[u]] == 0) --totColor;
}

int getAns() { return totColor; }

void dfs0(int u, int p) {
  L[u] = ++totdfn;
  Node[totdfn] = u;
  sz[u] = 1;
  for (int v : g[u])
    if (v != p) {
      dfs0(v, u);
      sz[u] += sz[v];
      if (!big[u] || sz[big[u]] < sz[v]) big[u] = v;
    }
  R[u] = totdfn;
}

void dfs1(int u, int p, bool keep) {
  // 计算轻儿子的答案
  for (int v : g[u])
    if (v != p && v != big[u]) {
      dfs1(v, u, false);
    }
  // 计算重儿子答案并保留计算过程中的数据（用于继承）
  if (big[u]) {
    dfs1(big[u], u, true);
  }
  for (int v : g[u])
    if (v != p && v != big[u]) {
      // 子树结点的 DFS 序构成一段连续区间，可以直接遍历
      for (int i = L[v]; i <= R[v]; i++) {
        add(Node[i]);
      }
    }
  add(u);
  ans[u] = getAns();
  if (keep == false) {
    for (int i = L[u]; i <= R[u]; i++) {
      del(Node[i]);
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs0(1, 0);
  dfs1(1, 0, false);
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]);
  return 0;
}

manacher

$p[i]$ ：以 $i$ 为中心的最长回文串长

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
int n;
char a[N], b[N];
int p[N];

void init()
{
    int k = 0;
    b[k ++ ] = '$', b[k ++ ] = '#';
    for (int i = 0; i < n; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
    b[k ++ ] = '^';
    n = k;
}

void manacher()
{
    int mr = 0, mid;
    for (int i = 1; i < n; i ++ )
    {
        if (i < mr) p[i] = min(p[mid * 2 - i], mr - i);
        else p[i] = 1;
        while (b[i - p[i]] == b[i + p[i]]) p[i] ++ ;
        if (i + p[i] > mr)
        {
            mr = i + p[i];
            mid = i;
        }
    }
}

int main()
{
    scanf("%s", a);
    n = strlen(a);

    init();
    manacher();

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, p[i]);
    printf("%d\n", res - 1);

    return 0;
}

分块(区间修改+区间查询)

  • $1,x,y,k$ ：$a[x,y]=a[x,y]+k$
  • $2,x,y$ ： $\sum a[x,y]$
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
int n, m, len;
LL add[M], sum[M];
int w[N];

int get(int i)
{
    return i / len;
}

void change(int l, int r, int d)
{
    if (get(l) == get(r))  // 段内直接暴力
    {
        for (int i = l; i <= r; i ++ ) w[i] += d, sum[get(i)] += d;
    }
    else
    {
        int i = l, j = r;
        while (get(i) == get(l)) w[i] += d, sum[get(i)] += d, i ++ ;
        while (get(j) == get(r)) w[j] += d, sum[get(j)] += d, j -- ;
        for (int k = get(i); k <= get(j); k ++ ) sum[k] += len * d, add[k] += d;
    }
}

LL query(int l, int r)
{
    LL res = 0;
    if (get(l) == get(r))  // 段内直接暴力
    {
        for (int i = l; i <= r; i ++ ) res += w[i] + add[get(i)];
    }
    else
    {
        int i = l, j = r;
        while (get(i) == get(l)) res += w[i] + add[get(i)], i ++ ;
        while (get(j) == get(r)) res += w[j] + add[get(j)], j -- ;
        for (int k = get(i); k <= get(j); k ++ ) res += sum[k];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    len = sqrt(n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &w[i]);
        sum[get(i)] += w[i];
    }

    char op[2];
    int l, r, d;
    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C')
        {
            scanf("%d", &d);
            change(l, r, d);
        }
        else printf("%lld\n", query(l, r));
    }

    return 0;
}