【左偏树】洛谷 P3377 【模板】左偏树（可并堆）
2021-03-24 17:46:00 # ACM

题链

运用$STL$

$STL$详解

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
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
//#pragma GCC optimize("O2")
using namespace std;
using namespace __gnu_pbds;
#define Pair pair<LL,LL>
#define Combine Pair, greater<Pair>, pairing_heap_tag
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 100009
#define INF 1e18
#define DBINF 1e100
#define Pi acos(-1.0)
#define eps 1e-9
#define mod 99999997

LL n,m;
LL fa[MS];
LL v[MS];
__gnu_pbds::priority_queue<Combine> Q[MS];

LL find(LL x){
	if(x == fa[x]) return x;
	else return fa[x] = find(fa[x]);
}

void merge(LL x,LL y){
	fa[find(y)] = find(x);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		LL x;
		cin >> x;
		Q[i].push({x,i});
		fa[i] = i;
	}
	while(m--){
		LL op,x,y;
		cin >> op;
		if(op == 1){
			cin >> x >> y;
			LL fx = find(x);
			LL fy = find(y);
			if(fx > fy) swap(fx,fy);
			if(fx == fy || v[x] || v[y]) continue;
			Q[fx].join(Q[fy]);
			merge(fx,fy);
		}
		else{
			cin >> x;
			if(v[x]){
				cout << -1 << "\n";
				continue;
			} 
			LL fx = find(x);
			Pair ans = Q[fx].top();
			v[ans.two] = 1;
			cout << ans.one << "\n";
			Q[fx].pop();
		}
	}



	return 0;
}

手写实现

题链

OI-wiki

有图好评

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
//#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#include<ext/rope>
using namespace __gnu_cxx;
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
#define Combine Pair, greater<Pair>, pairing_heap_tag
#define LL long long
#define ll long long
#define Pair pair<double,LL>
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 100009
#define INF 1e9
#define DBINF 1e100
#define Pi acos(-1.0)
#define eps 1e-9
#define mod 99999997
#define mod1 39989
#define mod2 1000000000

LL n,m;
struct node{
	LL fa,l,r;
	LL val,d;
}p[MS];
LL fa[MS];

LL find(LL x){
	if(x == p[x].fa) return x;
	else return p[x].fa = find(p[x].fa);
} 

LL merge(LL x,LL y){
	if(!x) return y;
	if(!y) return x;	
	if(
		p[x].val > p[y].val || 
		(p[x].val == p[y].val && x > y) // 保证有多个最小值时，优先删除先入队的 
	) swap(x,y);
	p[x].r = merge(p[x].r,y); // 多次递归合并右子树 
	if(p[p[x].r].d > p[p[x].l].d){ // 保证左子树的d值始终大于等于右子树 
		swap(p[x].l,p[x].r);
	}
	p[p[x].r].fa = p[p[x].l].fa = x; // 需要在多次递归后重定向fa的位置 
	
	p[x].d = p[p[x].r].d+1; // 更新d值 
	return x;
}

LL poptop(LL x){ 
	p[p[x].l].fa = p[x].l; // 将自己作为根，相当于合并两课子树 
	p[p[x].r].fa = p[x].r;
	p[x].val = -1; // 被删除值设为题给值范围外 
	p[x].fa = merge(p[x].l,p[x].r); // 将堆顶弹出后，该堆顶指向的父亲应该修改为它的孩子 
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	p[0].d = -1;
	for(int i=1;i<=n;i++){
		LL x;
		cin >> x;
		p[i] = {i,0,0,x,0};
	}
	while(m--){
		LL op,x,y;
		cin >> op;
		if(op == 1){
			cin >> x >> y;
			LL fx = find(x);
			LL fy = find(y);
			if(p[x].val == -1 || p[y].val == -1 || fx == fy) continue;
			merge(fx,fy);
		}
		else{
			cin >> x;
			if(p[x].val == -1) cout << -1 << endl;
			else{
				LL fx = find(x);
				cout << p[fx].val << endl;
				poptop(fx); // 删除该点 
			}
		}
	}
	
	
	
	return 0;
}
Prev
2021-03-24 17:46:00 # ACM
Next