【线段树分裂合并】洛谷 P5494 【模板】线段树分裂
2021-08-08 20:25:00 # ACM

题链

线段树分裂合并模板题

学习自BiliBili

关于线段树空间(带修改的)大概是: $2mlogn$

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
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 1000000007
	#define MAXN 1e18
	#define MS 200005

int n,m;
struct node{
	int l,r;
	LL val;
}p[MS*40];
int tot, rtpos[MS];

void push_up(int rt){
	p[rt].val = p[p[rt].l].val + p[p[rt].r].val;
}

void modify(int pos,int l,int r,int &rt,LL num){ // 单点修改 
	if(!rt) rt = ++tot;
	if(l == r){
		p[rt].val += num;
		return;
	}
	int m = l+r>>1;
	if(m >= pos) modify(pos,l,m,p[rt].l,num);
	else modify(pos,m+1,r,p[rt].r,num);
	push_up(rt);
}

int split(int L,int R,int l,int r,int &rt){ // 分裂： 将以 rt为根的树中 [L,R]区间提出来 
	int cc = ++tot;
	if(L <= l && r <= R){
		p[cc] = p[rt]; // 提出该节点对应区间 
		rt = 0; // 将该节点从原树中删除 
		return cc;
	}
	int m = l+r>>1;
	if(m >= L) p[cc].l = split(L,R,l,m,p[rt].l);
	if(m <  R) p[cc].r = split(L,R,m+1,r,p[rt].r);
	push_up(cc); // 更新新树 
	push_up(rt); // 更新原树 
	return cc;
}

void merge(int &x,int y){
	if(!x || !y){ // 如果两棵树该节点任意为空 
		x |= y; // x节点直接指向 y, 直接利用 y树的空间, 所以之后不能对 y重复操作, 相当于删除 y树 
		return;
	} 
	p[x].val += p[y].val; 
	merge(p[x].l,p[y].l); // 递归合并左右子树 
	merge(p[x].r,p[y].r);
}

LL query(int L,int R,int l,int r,int rt){ // 与普通线段树相同 
	if(!rt) return 0;
	if(L <= l && r <= R){
		return p[rt].val;
	}
	int m = l+r>>1;
	LL ans = 0;
	if(m >= L) ans += query(L,R,l,m,p[rt].l);
	if(m <  R) ans += query(L,R,m+1,r,p[rt].r);
	return ans;
}

int get_kth(int l,int r,int rt,LL kth){ // 类似主席树 
	if(l == r) return l;
	int m = l+r>>1;
	if(p[p[rt].l].val >= kth) return get_kth(l,m,p[rt].l,kth);
	else return get_kth(m+1,r,p[rt].r,kth-p[p[rt].l].val);
}

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		LL x;
		cin >> x;
		modify(i,1,n,rtpos[1],x);
	}
	int last = 1;
	while(m--){
		int op,x,y,z;
		cin >> op >> x >> y;
		if(op == 0){
			cin >> z;
			rtpos[++last] = split(y,z,1,n,rtpos[x]);
		}
		else if(op == 1){
			merge(rtpos[x],rtpos[y]);
		}
		else if(op == 2){
			cin >> z;
			modify(z,1,n,rtpos[x],y);
		}
		else if(op == 3){
			cin >> z;
			cout << query(y,z,1,n,rtpos[x]) << "\n";
		}
		else if(op == 4){
			if(p[rtpos[x]].val < y) cout << -1 << "\n";
			else cout << get_kth(1,n,rtpos[x],y) << "\n";
		}
	}
} 

int main() {
	ios::sync_with_stdio(false);
	int ce;
	ce = 1;
//	cin >> ce;
//	scanf("%d",&ce);
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/

Prev
2021-08-08 20:25:00 # ACM
Next