1 solutions
-
1
左偏树模板题
#include <bits/stdc++.h> using namespace std; const int N = 100010; int v[N], l[N], r[N], dis[N]; bool del[N]; int fa[N]; int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); } int cmp(int a, int b) { if (v[a] == v[b]) return a > b; return v[a] > v[b]; } int merge(int a, int b) { if ((!a) || (!b)) return a | b; if (cmp(a, b)) swap(a, b); r[a] = merge(r[a], b); if (dis[l[a]] < dis[r[a]]) swap(l[a], r[a]); dis[a] = dis[r[a]] + 1; return a; } int n, m; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i]; for (int i = 1; i <= n; i++) fa[i] = i; int opt, a, b; while (m--) { cin >> opt; if (opt == 1) { cin >> a >> b; if (del[a] || del[b]) continue; a = find(a), b = find(b); fa[a] = fa[b] = merge(a, b); } else { cin >> a; if (del[a]) { cout << -1 << '\n'; continue; } a = find(a); cout << v[a] << '\n'; fa[l[a]] = fa[r[a]] = fa[a] = merge(l[a], r[a]); del[a] = true; } } return 0; }
- 1
Information
- ID
- 2313
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 5
- Tags
- # Submissions
- 47
- Accepted
- 6
- Uploaded By