----可合并的优先队列 $O(nlog(n))$
1.模板题:合并堆,删除堆的最小值
P3377 【模板】左偏树/可并堆
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10, M = 1e3 + 10;
int val[N], ch[N][2], dis[N], fa[N];
// 外节点:节点 i 的左子树或右子树为空时,节点 i 被称为外节点。
// val[x]:存节点x的值
// ch[i][0]/[1]:第i层左/右子树
// dis[x]:节点的距离:节点x到后代中最近外节点的距离
// fa[x]:x的父节点
// 合并操作
int merge(int x, int y)
{
// 如果x 或 y已经被删掉了
if (val[x] == -1)
x = 0;
if (val[y] == -1)
y = 0;
// 如果其中一个节点被删了,那就保留另一棵树就好了
if (!x || !y)
return x + y;
// (小根堆)需要满足该节点的val不大于该节点左右儿子的val
if (val[x] > val[y] || (val[x] == val[y] && x > y))
swap(x, y);
// 合并右子树 和 y
ch[x][1] = merge(ch[x][1], y);
// 更新fa[]
fa[x] = fa[ch[x][1]] = fa[ch[x][0]] = x;
// 合并后 该节点的dis等于该节点右儿子的dis。
if (dis[ch[x][0]] < dis[ch[x][1]])
swap(ch[x][0], ch[x][1]);
// 该节点的dis等于该节点右儿子的dis+1
dis[x] = dis[ch[x][1]] + 1;
return x; // 返回父节点编号
}
// 删除操作
int pop(int x)
{
// 将左右子树的父节点修改为自己,
fa[ch[x][0]] = ch[x][0];
fa[ch[x][1]] = ch[x][1];
val[x] = -1; // 值置为-1
// 合并左右子树
int tt = merge(ch[x][0], ch[x][1]);
fa[x] = tt;
return tt;
}
int find(int x)
{
// 找父节点,路径压缩
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
signed main()
{
int n, m;
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
fa[i] = i;
// 刚开始每个节点当作一棵左偏树
for (int i = 1; i <= n; i++)
scanf("%lld", &val[i]);
while (m--)
{
dis[0] = -1;
int op, a, b;
scanf("%lld", &op);
if (op == 1)
{
scanf("%lld%lld", &a, &b);
// 若第x或第y个数已经被删除,无视此操作
if (val[a] == -1 || val[b] == -1)
continue;
// 第x和第y个数在用一个堆 ,就不能merge了
//自己节点挂在了自己节点下,链产生环了会导致后续find 函数里面爆栈
int pa = find(a), pb = find(b);
if (pa != pb)
merge(pa, pb);
}
else
{
scanf("%lld", &a);
if (val[a] == -1)
{
puts("-1");
continue;
}
// 找堆顶元素(父节点)
int pa = find(a);
printf("%lld\n", val[pa]);
pop(pa);
}
}
return 0;
}
2.取出最大值节点并修改其值,再合并回原来的堆中
P1456 Monkey King
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int val[N], ch[N][2], dis[N], fa[N];
int find(int x)
{
return fa[x] == x ? x : find(fa[x]);
}
int merge(int x, int y)
{
if (val[x] == -1)
x = 0;
if (val[y] == -1)
y = 0;
// 如果其中一个节点被删了,那就保留另一棵树就好了
if (!x || !y)
return x + y;
if (val[x] < val[y] || (val[x] == val[y] && x > y))
swap(x, y);
ch[x][1] = merge(ch[x][1], y);
fa[x] = fa[ch[x][1]] = fa[ch[x][0]] = x;
if (dis[ch[x][0]] < dis[ch[x][1]])
swap(ch[x][0], ch[x][1]);
dis[x] = dis[ch[x][1]] + 1;
return x;
}
int pop(int x)
{
fa[ch[x][0]] = ch[x][0];
fa[ch[x][1]] = ch[x][1];
val[x] = -1;
int tt = merge(ch[x][0], ch[x][1]);
fa[x] = tt;
return tt;
}
signed main()
{
int n;
while (~scanf("%lld", &n))
{
for (int i = 1; i <= n; i++)
scanf("%lld", &val[i]);
for (int i = 1; i <= n; i++)
fa[i] = i, ch[i][1] = ch[i][0] = 0;
int m;
scanf("%lld", &m);
while (m--)
{
int a, b;
scanf("%lld%lld", &a, &b);
int pa = find(a), pb = find(b);
if (pa == pb)
puts("-1");
else
{
// 合并最大值节点的左右子树, art为新节点
int art = merge(ch[pa][0], ch[pa][1]);
val[pa] /= 2; //修改最大值为原来一半
// 独立最大值节点pa
ch[pa][0] = ch[pa][1] = dis[pa] = 0;
// 新pa 与 旧pa的左右子树 合并
fa[pa] = merge(art, pa);
// 同理的修改最大值的操作
int brt = merge(ch[pb][0], ch[pb][1]);
val[pb] /= 2;
ch[pb][0] = ch[pb][1] = dis[pb] = 0;
fa[pb] = merge(brt, pb);
//两个堆分别完成最大值的修改,进行合并
int t = merge(find(pa), find(pb));
printf("%lld\n", val[t]);
}
}
}
return 0;
}