1382 字
7 分钟
左偏树 可并堆
左偏树 可并堆
左偏树是一种具有左偏性质的堆有序的二叉树。注意,左偏树不是二叉堆。
左偏树的每一个节点存储的信息包括左右子节点 、权值 和 距离 。
左儿子或右儿子为空的节点,称为外节点。节点的距离的定义:即该节点到与其最近的外节点经过的边数。
我们规定,外节点的距离为 0,空节点的距离为 -1。
[图片缺失:Pasted image 20260114153201.png]*左偏树实例
左偏树的性质
- 性质1:堆的性质,对于任意节点 (小根堆)。
- 性质2:左偏性质,左儿子的距离 右儿子的距离,。
- 性质3:任意节点的距离 = 其右儿子的距离 + 1,。
- 性质4:一棵有 个节点的二叉树,根的 。
性质4 的证明推导
因为根的距离为 的二叉树至少有 层是满二叉树,那么至少有 个节点。
即 ,所以 。
合并操作 (Merge)
合并操作是左偏树最重要的操作,过程主要包含两个维度的维护:
- 维护堆的性质: 先取值较小的那个根作为合并后的堆的根节点,然后递归合并其右儿子与另一个堆,作为合并后的堆的右儿子。
- 维护左偏性质: 合并后若左儿子的 小于右儿子的 (即 ),就交换两个儿子。
时间复杂度分析
由于左偏性质,每递归一层,其中一个堆根节点的 就会减小 1。
而一棵有 个节点的二叉树,根的 。
所以合并两个大小分别为 和 的堆的时间复杂度是 。
#include <bits/stdc++.h>#include <cstdlib>#include <utility>#define ll long long#define N 100005#define pr pair<ll, ll>using namespace std;ll k, n, m;class dsu { public: int fa[N]; void init() { for (int i = 1; i <= N; i++) fa[i] = i; } int find(int x) { return fa[x] = (fa[x] == x ? x : find(fa[x])); } bool merge(int x, int y) { int rx, ry; rx = find(x); ry = find(y); if (rx == ry) return 0; fa[rx] = ry; return 1; }} ds;class mergeable_heap { public: int val[N], rc[N], lc[N], dis[N], id = 0; int new_(int x) { val[++id] = x; return id; } int merge(int x, int y) { if (!x || !y) return x + y; if (make_pair(val[x], x) > make_pair(val[y], y)) swap(x, y); rc[x] = merge(rc[x], y); if (dis[rc[x]] > dis[lc[x]]) swap(lc[x], rc[x]); dis[x] = dis[rc[x]] + 1; return x; }} mh;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; ds.init(); for (int i = 1; i <= n; i++) { ll x; cin >> x; mh.new_(x); } mh.val[0] = -1; // 可能会合并到空节点 while (m--) { ll opt, x, y; cin >> opt; if (opt == 1) { cin >> x >> y; if (mh.val[x] == -1 || mh.val[y] == -1) continue; x = ds.find(x), y = ds.find(y); if (x != y) ds.fa[x] = ds.fa[y] = mh.merge(ds.find(x), ds.find(y)); } else { cin >> x; if (mh.val[x] == -1) cout << -1 << '\n'; else { x = ds.find(x); // 注意要判断的是这个点有无被删除,而不是这个点的祖先 cout << mh.val[x] << '\n'; mh.val[x] = -1; ds.fa[x] = ds.fa[mh.lc[x]] = ds.fa[mh.rc[x]] = mh.merge(mh.lc[x], mh.rc[x]); } } } return 0;}#include <bits/stdc++.h>#include <cmath>#include <cstdlib>#include <iomanip>#define ll long long#define N 200005#define M 2005#define pr pair<ll, ll>using namespace std;ll n, m, ans;class mergeable_heap { public: struct node { ll ls = 0, rs = 0, siz = 1, val = 0, sum = 0, dis = 0; } tr[N]; int root[N]; mergeable_heap() { tr[0].dis = -1; tr[0].siz = 0; } int id = 0; int new_(int x) { tr[++id] = {0, 0, 1, x, x}; return id; }#define lc tr[x] .ls#define rc tr[x] .rs int merge(int x, int y) { if (!x || !y) return x + y; if (make_pair(tr[x].val, x) < make_pair(tr[y].val, y)) swap(x, y); rc = merge(rc, y); if (tr[lc].dis < tr[rc].dis) swap(lc, rc); tr[x].dis = tr[rc].dis + 1; tr[x].siz = tr[lc].siz + tr[rc].siz + 1, tr[x].sum = tr[lc].sum + tr[rc].sum + tr[x].val; return x; } int del(int x) { int tem = merge(lc, rc); return tem; }} mheap;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; vector<ll> fa(n + 5, 0); vector<ll> pay(n + 5, 0); vector<ll> lead(n + 5, 0); vector<ll> root(n + 5, 0); for (int i = 1; i <= n; i++) { cin >> fa[i] >> pay[i] >> lead[i]; root[i] = mheap.new_(pay[i]); } for (int i = n; i >= 1; i--) { while (mheap.tr[root[i]].sum > m) { root[i] = mheap.del(root[i]); } ans = max(ans, lead[i] * mheap.tr[root[i]].siz); int fa_ = fa[i]; if (fa_) root[fa_] = mheap.merge(root[fa_], root[i]); } cout << ans; return 0;}P4331 [BalticOI 2004] Sequence (Day1)
#include <bits/stdc++.h>#include <cstdlib>#include <utility>#define ll long long#define N 1000005#define pr pair<ll, ll>using namespace std;ll n, ans, m, cnt;vector<ll> a;class mergeable_heap { public: struct node { int siz = 1, dis = 0, ls = 0, rs = 0, num = 0; } tr[N]; int id = 0; mergeable_heap() { tr[0].dis = -1; tr[0].siz = 0; } int new_(int x) { tr[++id].num = x; return id; }#define lc tr[x] .ls#define rc tr[x] .rs int merge(int x, int y) { if (!x || !y) return x + y; if (make_pair(a[tr[x].num], x) < make_pair(a[tr[y].num], y)) swap(x, y); rc = merge(rc, y); if (tr[lc].dis < tr[rc].dis) swap(lc, rc); tr[x].dis = tr[rc].dis + 1, tr[x].siz = tr[lc].siz + tr[rc].siz + 1; return x; } int del(int x) { int tem = merge(lc, rc); return tem; } int size(int x) { return tr[x].siz; }} mh;struct segment { int l, r, rt;} s[N];int top;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); cin >> n; a.assign(n + 5, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] -= i; } for (int i = 1; i <= n; i++) { s[++top] = {i, i, mh.new_(i)}; while (top > 1 && a[mh.tr[s[top - 1].rt].num] > a[mh.tr[s[top].rt].num]) { s[top - 1].rt = mh.merge(s[top - 1].rt, s[top].rt); s[top - 1].r = s[top].r; top--; while (mh.size(s[top].rt) > (s[top].r - s[top].l + 1) / 2 + 1) { s[top].rt = mh.del(s[top].rt); } } } vector<ll> ans; ll tol = 0; for (int i = 1; i <= top; i++) { for (int j = s[i].l; j <= s[i].r; j++) { ans.push_back(a[mh.tr[s[i].rt].num] + j); tol += abs(a[j] - a[mh.tr[s[i].rt].num]); } } cout << tol << '\n'; for (auto now : ans) cout << now << '\n'; return 0;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时