数据结构
普通并查集 DSU
// 普通并查集：路径压缩 + 按秩合并，点编号默认是 1..n。
class DSU
{
private:
vector<int> parent, rank, size;
int count;
public:
DSU(int n = 0)
{
init(n);
}
void init(int n)
{
parent.resize(n + 1);
rank.assign(n + 1, 0);
size.assign(n + 1, 1);
count = n;
iota(all(parent), 0ll);
}
int find(int x)
{
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
// 返回是否真的合并了两个原本不同的集合。
bool merge(int x, int y)
{
int rx = find(x), ry = find(y);
if (rx == ry)
{
return false;
}
if (rank[rx] < rank[ry])
{
swap(rx, ry);
}
parent[ry] = rx;
size[rx] += size[ry];
if (rank[rx] == rank[ry])
{
rank[rx]++;
}
count--;
return true;
}
bool issame(int x, int y)
{
return find(x) == find(y);
}
int getsize(int x)
{
return size[find(x)];
}
int getgroups()
{
return count;
}
};带权并查集
// ============================================================
// 带权并查集（维护点权之间的差）
// ============================================================
// 默认定义：
// weight[x] = value[x] - value[parent[x]]
//
// 路径压缩后：
// weight[x] = value[x] - value[root]
//
// merge(x, y, w) 加入的约束是：
// value[y] - value[x] = w
//
// diff(x, y) 返回：
// value[y] - value[x]
//
// 例子：
// merge(1, 2, 3) 表示 value[2] - value[1] = 3
// merge(2, 3, 5) 表示 value[3] - value[2] = 5
// diff(1, 3) 得到 8
//
// merge 的返回值：
// true ：成功合并，或者原有关系与新约束一致
// false ：x、y 已经连通，但新约束与原关系矛盾
//
// 换题时最容易改错的地方：
// 1. 有的题给的是 value[x] - value[y] = w。
// 此时调用 merge(x, y, -w)，不要同时修改多处公式。
// 2. 若维护异或关系，把“+ / -”整体换成 xor；
// 路径压缩和合并公式也必须一起推导，不能只改 diff()。
// 3. 食物链这类模 k 关系：所有 weight 和 w 都需要规范到 [0, k)。
// 相加、相减后也要取模。
// 4. 带权并查集只能维护同一连通块内的相对关系，不能直接得到绝对值。
//
// 合并公式推导（默认把 ry 接到 rx 时）：
// wx = value[x] - value[rx]
// wy = value[y] - value[ry]
// 又有 value[y] - value[x] = w
// 所以 value[ry] - value[rx] = w + wx - wy
// 即 weight[ry] = w + wx - wy
// ============================================================
class WeightedDSU
{
private:
vector<int> parent, rank, size;
vector<int> weight;
int count;
public:
WeightedDSU(int n)
: parent(n + 1), rank(n + 1), size(n + 1, 1),
weight(n + 1), count(n)
{
iota(all(parent), 0ll);
}
int find(int x)
{
if (parent[x] == x)
{
return x;
}
int old_parent = parent[x];
parent[x] = find(parent[x]);
weight[x] += weight[old_parent];
return parent[x];
}
bool merge(int x, int y, int w)
{
int rx = find(x), ry = find(y);
int wx = weight[x], wy = weight[y];
if (rx == ry)
{
return wy - wx == w;
}
if (rank[rx] < rank[ry])
{
parent[rx] = ry;
weight[rx] = wy - wx - w;
size[ry] += size[rx];
}
else
{
parent[ry] = rx;
weight[ry] = w + wx - wy;
size[rx] += size[ry];
if (rank[rx] == rank[ry])
{
rank[rx]++;
}
}
count--;
return true;
}
bool issame(int x, int y)
{
return find(x) == find(y);
}
// 调用前应保证 issame(x, y) 为 true。
int diff(int x, int y)
{
find(x);
find(y);
return weight[y] - weight[x];
}
bool check(int x, int y, int w)
{
return issame(x, y) and diff(x, y) == w;
}
int getweight(int x)
{
find(x);
return weight[x];
}
int getsize(int x)
{
return size[find(x)];
}
int getgroups()
{
return count;
}
};树状数组 BIT
// ============================================================
// 树状数组（全部使用 1 下标）
// ============================================================
// BIT 支持：单点加、单点赋值、前缀和、区间和、前缀 lower_bound。
// RangeBIT 支持：区间加、前缀和、区间和、单点查询。
//
// kth(target) 返回最小的 pos，使 sum(pos) >= target。
// 它要求树状数组维护的是非负频次，否则前缀和不单调，不能二分。
// 若 target > sum(n)，返回 n + 1。
// ============================================================
class BIT
{
private:
int n;
vector<int> c;
int lowbit(int x)
{
return x & -x;
}
public:
BIT(int size = 0) : n(size), c(n + 1)
{
}
// arr 使用 1 下标，有效元素为 arr[1..n]，arr[0] 空置。
BIT(const vector<int> &arr) : n(arr.size() - 1), c(n + 1)
{
for (int i = 1; i <= n; i++)
{
add(i, arr[i]);
}
}
void init(int size)
{
n = size;
c.assign(n + 1, 0);
}
void add(int i, int val)
{
while (i <= n)
{
c[i] += val;
i += lowbit(i);
}
}
int sum(int i)
{
int ans = 0;
while (i > 0)
{
ans += c[i];
i -= lowbit(i);
}
return ans;
}
int query(int l, int r)
{
if (l > r)
{
return 0;
}
return sum(r) - sum(l - 1);
}
int get(int i)
{
return query(i, i);
}
void update(int i, int val)
{
int delta = val - get(i);
add(i, delta);
}
int kth(int target)
{
if (target <= 0)
{
return 1;
}
int pos = 0;
int pre = 0;
int step = 1;
while ((step << 1) <= n)
{
step <<= 1;
}
for (; step; step >>= 1)
{
int nxt = pos + step;
if (nxt <= n and pre + c[nxt] < target)
{
pos = nxt;
pre += c[nxt];
}
}
return pos + 1;
}
void clear()
{
fill(all(c), 0);
}
int size()
{
return n;
}
};
class RangeBIT
{
private:
int n;
BIT c1, c2;
void add(BIT &c, int pos, int val)
{
if (pos <= n)
{
c.add(pos, val);
}
}
public:
RangeBIT(int n = 0) : n(n), c1(n), c2(n)
{
}
// 在 [l, r] 全部增加 val。
void add(int l, int r, int val)
{
add(c1, l, val);
add(c1, r + 1, -val);
add(c2, l, val * (l - 1));
add(c2, r + 1, -val * r);
}
int sum(int pos)
{
return c1.sum(pos) * pos - c2.sum(pos);
}
int query(int l, int r)
{
if (l > r)
{
return 0;
}
return sum(r) - sum(l - 1);
}
int get(int pos)
{
return query(pos, pos);
}
};线段树 SegTree
// ============================================================
// 通用线段树（数组使用 1 下标）
// ============================================================
// 当前支持：
// 1. 区间加：add(l, r, val)
// 2. 区间赋值：change(l, r, val)
// 3. 区间取 min：setmin(l, r, val)，即 a[i] = min(a[i], val)
// 4. 区间取 max：setmax(l, r, val)，即 a[i] = max(a[i], val)
// 5. 区间和：getsum(l, r)
// 6. 区间最小值：getmin(l, r)
// 7. 区间最大值：getmax(l, r)
// 8. 单点赋值：modify(pos, val)
// 9. 单点查询：get(pos)
// 10. 在区间内寻找第一个/最后一个值 >= val 的位置
//
// 默认语义：
// change 是“覆盖”，add 是“在当前值上增加”。
// 若同一节点先 change 再 add，下传时也必须先下传 change，再下传 add。
// 这是 down() 中两个懒标记顺序不能交换的原因。
//
// 换题时常见改动：
// 1. 只需要 add + getsum：可以删除 mmin、mmax、ch、has_ch 相关代码。
// 2. 只需要 add + getmax/getmin：可以删除 sum；lazy_add 不再需要 len。
// 3. 只需要 change：可以删除 ad 和 lazy_add。
// 4. 求区间乘积、gcd 等：重点修改 up() 和查询时的合并方式；
// 但区间 add 通常不能直接维护 gcd/乘积，不能只改变量名。
// 5. 找第一个满足条件的位置：find_first_ge 依赖“区间最大值”。
// 如果改成寻找 <= val，应改用 mmin 剪枝。
//
// 注意：
// - 构造函数 SegTree(vector<int> &v) 要求 v 的有效元素是 v[1..n]。
// - n 必须至少为 1。
// - 若题目中的值和区间和可能超过 long long，需要改成 __int128。
// ============================================================
class SegTree
{
private:
int n;
// sum[i]、mmin[i]、mmax[i] 分别记录节点 i 所管区间的和、最小值、最大值。
vector<int> sum, mmin, mmax;
// smn/smx：严格次小值/严格次大值；cmn/cmx：最小值/最大值出现次数。
// 这些信息用于 Segment Tree Beats，在不下沉到叶子的情况下完成区间 chmin/chmax。
vector<int> smn, smx, cmn, cmx;
// ad[i]：节点 i 所管区间整体还要增加多少，尚未下传给儿子。
// ch[i]：节点 i 所管区间整体要被赋成什么值。
// has_ch[i]：不能用 ch[i] 是否为 0 判断赋值标记，因为“赋值为 0”也是合法操作。
vector<int> ad, ch;
vector<int> has_ch;
// 保存建树时使用的原数组，有效范围是 v[1..n]。
vector<int> v;
// 把“整个节点 i 所管区间增加 val”直接作用到节点信息上。
// len 是该节点所管区间长度：区间和增加 val * len，最值只增加 val。
// 这里只更新当前节点并累计懒标记，不立刻递归修改它的儿子。
void lazy_add(int i, int val, int len)
{
sum[i] += val * len;
mmin[i] += val;
mmax[i] += val;
if (smn[i] != LLONG_MAX)
smn[i] += val;
if (smx[i] != LLONG_MIN)
smx[i] += val;
// 已有赋值标记时直接合并到赋值值，保持 has_ch 与 ad 不同时存在。
// 这能让后续 setmin/setmax 与 change/add 的组合保持唯一语义。
if (has_ch[i])
ch[i] += val;
else
ad[i] += val;
}
// 把“整个节点 i 所管区间赋值为 val”直接作用到节点信息上。
// 赋值会覆盖此前尚未下传的加法，所以必须把 ad[i] 清零。
// has_ch[i] 设为 1，表示以后 down() 时需要把赋值继续传给两个儿子。
void lazy_change(int i, int val, int len)
{
sum[i] = val * len;
mmin[i] = mmax[i] = val;
smn[i] = LLONG_MAX;
smx[i] = LLONG_MIN;
cmn[i] = cmx[i] = len;
ch[i] = val;
ad[i] = 0;
has_ch[i] = 1;
}
// 前提：smx[i] < val < mmax[i]。只有当前最大值会被压低到 val。
void lazy_setmin(int i, int val)
{
if (mmax[i] <= val)
return;
sum[i] += (val - mmax[i]) * cmx[i];
if (mmin[i] == mmax[i])
mmin[i] = val;
else if (smn[i] == mmax[i])
smn[i] = val;
mmax[i] = val;
if (has_ch[i])
ch[i] = val;
}
// 前提：mmin[i] < val < smn[i]。只有当前最小值会被抬高到 val。
void lazy_setmax(int i, int val)
{
if (mmin[i] >= val)
return;
sum[i] += (val - mmin[i]) * cmn[i];
if (mmax[i] == mmin[i])
mmax[i] = val;
else if (smx[i] == mmin[i])
smx[i] = val;
mmin[i] = val;
if (has_ch[i])
ch[i] = val;
}
// 用两个儿子的信息重新计算父节点 i。
// 每次对子区间递归修改完成后，都要调用 up(i)。
void up(int i)
{
sum[i] = sum[i << 1] + sum[i << 1 | 1];
if (mmax[i << 1] == mmax[i << 1 | 1])
{
mmax[i] = mmax[i << 1];
cmx[i] = cmx[i << 1] + cmx[i << 1 | 1];
smx[i] = max(smx[i << 1], smx[i << 1 | 1]);
}
else if (mmax[i << 1] > mmax[i << 1 | 1])
{
mmax[i] = mmax[i << 1];
cmx[i] = cmx[i << 1];
smx[i] = max(smx[i << 1], mmax[i << 1 | 1]);
}
else
{
mmax[i] = mmax[i << 1 | 1];
cmx[i] = cmx[i << 1 | 1];
smx[i] = max(mmax[i << 1], smx[i << 1 | 1]);
}
if (mmin[i << 1] == mmin[i << 1 | 1])
{
mmin[i] = mmin[i << 1];
cmn[i] = cmn[i << 1] + cmn[i << 1 | 1];
smn[i] = min(smn[i << 1], smn[i << 1 | 1]);
}
else if (mmin[i << 1] < mmin[i << 1 | 1])
{
mmin[i] = mmin[i << 1];
cmn[i] = cmn[i << 1];
smn[i] = min(smn[i << 1], mmin[i << 1 | 1]);
}
else
{
mmin[i] = mmin[i << 1 | 1];
cmn[i] = cmn[i << 1 | 1];
smn[i] = min(mmin[i << 1], smn[i << 1 | 1]);
}
}
// 把节点 i 上尚未下传的懒标记传给左右儿子。
// ln、rn 分别是左儿子、右儿子所管区间的长度。
// 必须先传 change 再传 add，因为赋值会覆盖旧值，加法是在赋值后的新值上继续增加。
void down(int i, int ln, int rn)
{
if (has_ch[i])
{
lazy_change(i << 1, ch[i], ln);
lazy_change(i << 1 | 1, ch[i], rn);
has_ch[i] = 0;
}
if (ad[i])
{
lazy_add(i << 1, ad[i], ln);
lazy_add(i << 1 | 1, ad[i], rn);
ad[i] = 0;
}
// 父节点可能做过 chmin/chmax；把父节点的新上下界同步给儿子。
if (mmax[i << 1] > mmax[i])
lazy_setmin(i << 1, mmax[i]);
if (mmax[i << 1 | 1] > mmax[i])
lazy_setmin(i << 1 | 1, mmax[i]);
if (mmin[i << 1] < mmin[i])
lazy_setmax(i << 1, mmin[i]);
if (mmin[i << 1 | 1] < mmin[i])
lazy_setmax(i << 1 | 1, mmin[i]);
}
// 建立当前节点 i，它负责原数组区间 [l, r]。
// 到达叶子时，直接读取 v[l]；否则递归建立两个儿子后调用 up(i)。
void build(int l, int r, int i)
{
ad[i] = ch[i] = has_ch[i] = 0;
if (l == r)
{
sum[i] = mmin[i] = mmax[i] = v[l];
smn[i] = LLONG_MAX;
smx[i] = LLONG_MIN;
cmn[i] = cmx[i] = 1;
return;
}
int mid = (l + r) >> 1;
build(l, mid, i << 1);
build(mid + 1, r, i << 1 | 1);
up(i);
}
// 递归执行区间加。
// jobl、jobr：本次真正想修改的目标区间。
// l、r ：当前节点 i 所管的区间。
// i ：当前线段树节点编号，左儿子 i<<1，右儿子 i<<1|1。
void add(int jobl, int jobr, int val, int l, int r, int i)
{
if (jobl <= l and r <= jobr)
{
lazy_add(i, val, r - l + 1);
return;
}
int mid = (l + r) >> 1;
down(i, mid - l + 1, r - mid);
if (jobl <= mid)
{
add(jobl, jobr, val, l, mid, i << 1);
}
if (jobr > mid)
{
add(jobl, jobr, val, mid + 1, r, i << 1 | 1);
}
up(i);
}
// 递归执行区间赋值，参数含义与上面的 add 相同。
// 如果当前区间被目标区间完整覆盖，就打 change 懒标记，不再继续向下递归。
void change(int jobl, int jobr, int val, int l, int r, int i)
{
if (jobl <= l and r <= jobr)
{
lazy_change(i, val, r - l + 1);
return;
}
int mid = (l + r) >> 1;
down(i, mid - l + 1, r - mid);
if (jobl <= mid)
{
change(jobl, jobr, val, l, mid, i << 1);
}
if (jobr > mid)
{
change(jobl, jobr, val, mid + 1, r, i << 1 | 1);
}
up(i);
}
void setmin(int jobl, int jobr, int val, int l, int r, int i)
{
if (mmax[i] <= val)
return;
if (jobl <= l and r <= jobr and smx[i] < val)
{
lazy_setmin(i, val);
return;
}
int mid = (l + r) >> 1;
down(i, mid - l + 1, r - mid);
if (jobl <= mid)
setmin(jobl, jobr, val, l, mid, i << 1);
if (jobr > mid)
setmin(jobl, jobr, val, mid + 1, r, i << 1 | 1);
up(i);
}
void setmax(int jobl, int jobr, int val, int l, int r, int i)
{
if (mmin[i] >= val)
return;
if (jobl <= l and r <= jobr and smn[i] > val)
{
lazy_setmax(i, val);
return;
}
int mid = (l + r) >> 1;
down(i, mid - l + 1, r - mid);
if (jobl <= mid)
setmax(jobl, jobr, val, l, mid, i << 1);
if (jobr > mid)
setmax(jobl, jobr, val, mid + 1, r, i << 1 | 1);
up(i);
}
// 递归查询目标区间 [jobl, jobr] 的区间和。
// 查询前调用 down()，保证儿子的信息包含父节点此前积累的懒标记。
int getsum(int jobl, int jobr, int l, int r, int i)
{
if (jobl <= l and r <= jobr)
{
return sum[i];
}
int mid = (l + r) >> 1;
down(i, mid - l + 1, r - mid);
int ans = 0;
if (jobl <= mid)
{
ans += getsum(jobl, jobr, l, mid, i << 1);
}
if (jobr > mid)
{
ans += getsum(jobl, jobr, mid + 1, r, i << 1 | 1);
}
return ans;
}
// 递归查询目标区间 [jobl, jobr] 的最小值。
// ans 初始为正无穷，因为 min(正无穷, 合法答案) 仍是合法答案。
int getmin(int jobl, int jobr, int l, int r, int i)
{
if (jobl <= l and r <= jobr)
{
return mmin[i];
}
int mid = (l + r) >> 1;
down(i, mid - l + 1, r - mid);
int ans = LLONG_MAX;
if (jobl <= mid)
{
ans = min(ans, getmin(jobl, jobr, l, mid, i << 1));
}
if (jobr > mid)
{
ans = min(ans, getmin(jobl, jobr, mid + 1, r, i << 1 | 1));
}
return ans;
}
// 递归查询目标区间 [jobl, jobr] 的最大值。
// ans 初始为负无穷，因为 max(负无穷, 合法答案) 仍是合法答案。
int getmax(int jobl, int jobr, int l, int r, int i)
{
if (jobl <= l and r <= jobr)
{
return mmax[i];
}
int mid = (l + r) >> 1;
down(i, mid - l + 1, r - mid);
int ans = LLONG_MIN;
if (jobl <= mid)
{
ans = max(ans, getmax(jobl, jobr, l, mid, i << 1));
}
if (jobr > mid)
{
ans = max(ans, getmax(jobl, jobr, mid + 1, r, i << 1 | 1));
}
return ans;
}
// 在 [jobl, jobr] 中寻找最靠左且数组值 >= val 的位置，不存在返回 -1。
// 如果当前区间与目标区间无交集，或者当前区间最大值都小于 val，可以直接剪枝。
// 先递归左儿子，只有左边找不到时才找右边，因此得到的是“第一个位置”。
int find_first_ge(int jobl, int jobr, int val, int l, int r, int i)
{
if (r < jobl or jobr < l or mmax[i] < val)
{
return -1;
}
if (l == r)
{
return l;
}
int mid = (l + r) >> 1;
down(i, mid - l + 1, r - mid);
int ans = find_first_ge(jobl, jobr, val, l, mid, i << 1);
if (ans == -1)
{
ans = find_first_ge(jobl, jobr, val, mid + 1, r, i << 1 | 1);
}
return ans;
}
// 在 [jobl, jobr] 中寻找最靠右且数组值 >= val 的位置，不存在返回 -1。
// 与 find_first_ge 相同，只是优先递归右儿子，因此得到的是“最后一个位置”。
int find_last_ge(int jobl, int jobr, int val, int l, int r, int i)
{
if (r < jobl or jobr < l or mmax[i] < val)
{
return -1;
}
if (l == r)
{
return l;
}
int mid = (l + r) >> 1;
down(i, mid - l + 1, r - mid);
int ans = find_last_ge(jobl, jobr, val, mid + 1, r, i << 1 | 1);
if (ans == -1)
{
ans = find_last_ge(jobl, jobr, val, l, mid, i << 1);
}
return ans;
}
public:
// 建立一个长度为 n、初始值全部为 0 的线段树。
SegTree(int n) : n(n), sum(n << 2), mmin(n << 2), mmax(n << 2),
smn(n << 2), smx(n << 2), cmn(n << 2), cmx(n << 2),
ad(n << 2), ch(n << 2), has_ch(n << 2), v(n + 1)
{
build(1, n, 1);
}
// 根据 1 下标数组 v 建树：v[0] 空置，有效元素为 v[1..n]。
SegTree(vector<int> &v) : n(v.size() - 1), sum(n << 2), mmin(n << 2),
mmax(n << 2), smn(n << 2), smx(n << 2),
cmn(n << 2), cmx(n << 2), ad(n << 2), ch(n << 2),
has_ch(n << 2), v(v)
{
build(1, n, 1);
}
// 对闭区间 [l, r] 的每个数增加 val。
void add(int l, int r, int val)
{
add(l, r, val, 1, n, 1);
}
// 把闭区间 [l, r] 的每个数全部赋值为 val。
void change(int l, int r, int val)
{
if (l > r)
return;
change(l, r, val, 1, n, 1);
}
// 对闭区间 [l, r] 执行 a[i] = min(a[i], val)。
void setmin(int l, int r, int val)
{
if (l > r)
return;
setmin(l, r, val, 1, n, 1);
}
// 对闭区间 [l, r] 执行 a[i] = max(a[i], val)。
void setmax(int l, int r, int val)
{
if (l > r)
return;
setmax(l, r, val, 1, n, 1);
}
// 单点赋值：把下标 pos 的值改成 val。
void modify(int pos, int val)
{
change(pos, pos, val);
}
// 返回闭区间 [l, r] 的元素和。
int getsum(int l, int r)
{
return getsum(l, r, 1, n, 1);
}
// 返回闭区间 [l, r] 的最小值。
int getmin(int l, int r)
{
return getmin(l, r, 1, n, 1);
}
// 返回闭区间 [l, r] 的最大值。
int getmax(int l, int r)
{
return getmax(l, r, 1, n, 1);
}
// 返回下标 pos 当前的值。
int get(int pos)
{
return getsum(pos, pos);
}
// 返回 [l, r] 内第一个值 >= val 的下标，不存在返回 -1。
int find_first_ge(int l, int r, int val)
{
return find_first_ge(l, r, val, 1, n, 1);
}
// 返回 [l, r] 内最后一个值 >= val 的下标，不存在返回 -1。
int find_last_ge(int l, int r, int val)
{
return find_last_ge(l, r, val, 1, n, 1);
}
// 兼容旧模板：update 表示区间加，query 表示区间和。
void update(int l, int r, int val)
{
add(l, r, val);
}
int query(int l, int r)
{
return getsum(l, r);
}
// 返回当前维护的数组长度。
int size()
{
return n;
}
};左偏树与可并堆
// ============================================================
// 左偏树（可并堆 / Mergeable Heap，节点编号从 1 开始）
// ============================================================
// 支持：
// 1. newnode(val) 新建一个只有一个节点的堆，返回节点编号
// 2. merge(x, y) 合并两个堆，返回新根
// 3. push(root, val) 插入元素，返回新根
// 4. top(root) 查询堆顶值
// 5. top_id(root) 查询堆顶节点编号
// 6. pop(root) 删除堆顶，返回新根
// 7. add_all(root, val) 整个堆的所有值增加 val
// 8. size(root) / empty(root) 查询大小 / 判空
//
// 默认是小根堆：
// LeftistTree<int> heap;
// 改成大根堆：
// LeftistTree<int, greater<int>> heap;
//
// 左偏树性质：
// dis[x] 表示 x 到最近空儿子的距离，规定 dis[0] = 0。
// 始终保持 dis[ls[x]] >= dis[rs[x]]，因此右链长度为 O(log n)。
// merge 是所有操作的核心，单次合并 / 插入 / 删除堆顶均为 O(log n)。
//
// 重要约束：
// - merge(x, y) 要求 x、y 是两个互不相交的堆，否则会形成环。
// - pop(root) 后旧根已经删除，不要继续把旧根当成合法堆使用。
// - add_all 是“整堆统一加”，不会改变堆内相对大小，因此可以懒标记。
// - 若只需要最基础左偏树，可删除 lazy、apply、down、add_all。
// - 值相同时按节点编号小的优先，方便题目要求稳定判定。
// ============================================================
template <class T = int, class Compare = less<T>>
class LeftistTree
{
private:
vector<T> val, lazy;
vector<int> ls, rs, dis, siz;
vector<char> deleted;
Compare cmp;
// a 是否应该排在 b 前面。
// 小根堆时值小的优先，大根堆时值大的优先；值相同则编号小的优先。
bool better(int a, int b) const
{
if (cmp(val[a], val[b]))
{
return true;
}
if (cmp(val[b], val[a]))
{
return false;
}
return a < b;
}
void apply(int x, const T &v)
{
if (!x)
{
return;
}
val[x] += v;
lazy[x] += v;
}
void down(int x)
{
if (!x or lazy[x] == T{})
{
return;
}
apply(ls[x], lazy[x]);
apply(rs[x], lazy[x]);
lazy[x] = T{};
}
void up(int x)
{
if (dis[ls[x]] < dis[rs[x]])
{
swap(ls[x], rs[x]);
}
dis[x] = dis[rs[x]] + 1;
siz[x] = siz[ls[x]] + siz[rs[x]] + 1;
}
public:
LeftistTree(int reserve_n = 0)
{
val.reserve(reserve_n + 1);
lazy.reserve(reserve_n + 1);
ls.reserve(reserve_n + 1);
rs.reserve(reserve_n + 1);
dis.reserve(reserve_n + 1);
siz.reserve(reserve_n + 1);
deleted.reserve(reserve_n + 1);
// 0 号节点表示空节点。
val.push_back(T{});
lazy.push_back(T{});
ls.push_back(0);
rs.push_back(0);
dis.push_back(0);
siz.push_back(0);
deleted.push_back(1);
}
// 新建单点堆并返回节点编号。
int newnode(const T &v)
{
int id = val.size();
val.push_back(v);
lazy.push_back(T{});
ls.push_back(0);
rs.push_back(0);
dis.push_back(1);
siz.push_back(1);
deleted.push_back(0);
return id;
}
// 合并两个互不相交的堆，返回新根。
int merge(int x, int y)
{
if (!x or !y)
{
return x | y;
}
if (!better(x, y))
{
swap(x, y);
}
down(x);
rs[x] = merge(rs[x], y);
up(x);
return x;
}
// 向 root 所在堆插入一个值，返回新根。
int push(int root, const T &v)
{
return merge(root, newnode(v));
}
// 查询堆顶值；调用者须保证 root != 0。
const T &top(int root) const
{
return val[root];
}
int top_id(int root) const
{
return root;
}
// 删除堆顶并返回新根。
int pop(int root)
{
down(root);
int x = ls[root], y = rs[root];
ls[root] = rs[root] = 0;
dis[root] = siz[root] = 0;
deleted[root] = 1;
return merge(x, y);
}
// 整个堆统一增加 v，O(1)。
void add_all(int root, const T &v)
{
apply(root, v);
}
int size(int root) const
{
return siz[root];
}
bool empty(int root) const
{
return root == 0;
}
bool alive(int id) const
{
return id > 0 and id < (int)deleted.size() and !deleted[id];
}
int nodes() const
{
return (int)val.size() - 1;
}
};
// ============================================================
// 常见用法 1：维护若干个“根编号”
// ============================================================
/*
LeftistTree<int> heap(n);
vector<int> root(k + 1);
root[1] = heap.push(root[1], 10);
root[1] = heap.push(root[1], 3);
root[2] = heap.push(root[2], 7);
root[1] = heap.merge(root[1], root[2]);
root[2] = 0; // 两个堆已经合并，原来的 root[2] 必须作废。
cout << heap.top(root[1]) << endl; // 3
root[1] = heap.pop(root[1]);
cout << heap.top(root[1]) << endl; // 7
*/
// ============================================================
// 常见用法 2：每个初始节点属于一个可合并堆（P3377 类型）
// ============================================================
// 这种题通常有两种操作：
// merge_set(x, y)：合并 x、y 当前所属的堆；
// pop_set(x) ：删除 x 当前所属堆的堆顶，并返回 {堆顶编号, 堆顶值}。
//
// 注意：
// 删除堆顶后，并查集代表元需要改成新的堆根。
// 已删除节点再次参与操作时，本封装直接忽略。
// 该封装不提供 add_all；如果题目同时需要整堆加，根映射需按题意额外维护。
// ============================================================
template <class T = int, class Compare = less<T>>
class MergeableHeap
{
private:
LeftistTree<T, Compare> heap;
vector<int> fa;
vector<char> removed;
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
public:
// a 必须是 1 下标数组，有效范围 a[1..n]。
MergeableHeap(const vector<T> &a) : heap((int)a.size() - 1)
{
int n = (int)a.size() - 1;
fa.resize(n + 1);
removed.assign(n + 1, 0);
fa[0] = 0;
for (int i = 1; i <= n; i++)
{
int id = heap.newnode(a[i]);
fa[i] = id;
}
}
bool alive(int x) const
{
return x > 0 and x < (int)removed.size() and !removed[x];
}
// 合并 x、y 所属的堆；任一点已删除时忽略。
void merge_set(int x, int y)
{
if (!alive(x) or !alive(y))
{
return;
}
int rx = find(x), ry = find(y);
if (rx == ry)
{
return;
}
int root = heap.merge(rx, ry);
fa[rx] = fa[ry] = fa[root] = root;
}
// 返回 x 所属堆的堆顶编号；x 已删除时返回 -1。
int top_id(int x)
{
return alive(x) ? find(x) : -1;
}
// 返回 x 所属堆的堆顶值；调用者须保证 x 未删除。
const T &top(int x)
{
return heap.top(find(x));
}
// 删除 x 所属堆的堆顶，返回 {被删编号, 被删值}。
// x 已删除时返回 {-1, T{}}。
pair<int, T> pop_set(int x)
{
if (!alive(x))
{
return {-1, T{}};
}
int oldroot = find(x);
T answer = heap.top(oldroot);
int newroot = heap.pop(oldroot);
removed[oldroot] = 1;
fa[oldroot] = newroot;
if (newroot)
{
fa[newroot] = newroot;
}
return {oldroot, answer};
}
};
// ============================================================
// P3377 类型 solve 示例
// ============================================================
/*
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
MergeableHeap<int> heap(a);
while (m--)
{
int op, x, y;
cin >> op >> x;
if (op == 1)
{
cin >> y;
heap.merge_set(x, y);
}
else
{
auto [id, value] = heap.pop_set(x);
if (id == -1)
{
cout << -1 << endl;
}
else
{
cout << value << endl;
}
}
}
}
*/