堆（Heap）

参考资料

堆简介 - OI Wiki

左偏树

struct Node
{
	int val,ls,rs,dis;
}t[N];
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(t[x].val>t[y].val||(t[x].val==t[y].val&&x>y))swap(x,y);
	t[x].rs=merge(t[x].rs,y);
	if(t[t[x].ls].dis<t[t[x].rs].dis)swap(t[x].ls,t[x].rs);
	t[x].dis=t[t[x].rs].dis+1;
	return x;
}

pb_ds

__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int>>> q[N];

例题

洛谷 P3377 【模板】左偏树/可并堆

有 $n$ 个小根堆，每个堆包含一个数。需要支持两种操作：

1 x y：将第 $x$ 个数和第 $y$ 个数所在的小根堆合并（若 $x$ 或 $y$ 已经被删除或 $x$ 和 $y$ 在同一个堆内，则无视此操作）。
2 x：输出第 $x$ 个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第 $x$ 个数已经被删除，则输出 -1 并无视删除操作）。

左偏树
pb_ds

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
struct Node
{
	int val,ls,rs,dis;
}t[N];
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(t[x].val>t[y].val||(t[x].val==t[y].val&&x>y))swap(x,y);
	t[x].rs=merge(t[x].rs,y);
	if(t[t[x].ls].dis<t[t[x].rs].dis)swap(t[x].ls,t[x].rs);
	t[x].dis=t[t[x].rs].dis+1;
	return x;
}
bool del[N];
int fa[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int v;
		cin>>v;
		t[i].val=v;
		fa[i]=i;
	}
	while(m--)
	{
		int op,x,y;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y;
			if(del[x]||del[y])continue;
			x=find(x);y=find(y);
			if(x==y)continue;
			fa[x]=fa[y]=merge(x,y);
		}
		else if(op==2)
		{
			cin>>x;
			if(del[x])
			{
				cout<<"-1"<<'\n';
				continue;
			}
			x=find(x);
			cout<<t[x].val<<'\n';
			del[x]=1;
			fa[x]=fa[t[x].ls]=fa[t[x].rs]=merge(t[x].ls,t[x].rs);
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

const int N=100005;
__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int>>> q[N];
bool del[N];
int fa[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int v;
		cin>>v;
		q[i].push({v,i});
		fa[i]=i;
	}
	while(m--)
	{
		int op,x,y;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y;
			if(del[x]||del[y])continue;
			x=find(x);y=find(y);
			if(x==y)continue;
			q[x].join(q[y]);
			fa[y]=x;
		}
		else if(op==2)
		{
			cin>>x;
			if(del[x])
			{
				cout<<"-1"<<'\n';
				continue;
			}
			x=find(x);
			cout<<q[x].top().first<<'\n';
			del[q[x].top().second]=1;
			q[x].pop();
		}
	}
	return 0;
}

洛谷 P2713 罗马游戏

罗马皇帝的军队 $n$ 个士兵，每个士兵都是一个独立的团，每个士兵都有一个分数。

皇帝很喜欢平面几何，他对那些得分很低的士兵嗤之以鼻。

他决定玩这样一个游戏。他可以发两种命令：

M i j：把 $i$ 所在的团和 $j$ 所在的团合并成一个团。如果 $i,j$ 有一个士兵是死人，那么就忽略该命令。
K i：把 $i$ 所在的团里面得分最低的士兵杀死。如果 $i$ 这个士兵已经死了，这条命令就忽略。

皇帝希望他每发布一条 K i 命令，下面的将军就把被杀的士兵的分数报上来（如果这条命令被忽略，那么就报 $0$ 分）。

保证士兵的分数互不相同。

#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
struct Node
{
	int ls,rs,val,dis;
	Node():ls(0),rs(0),val(0),dis(-1){}
	Node(int v):ls(0),rs(0),val(v),dis(0){}
}t[N];
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(t[x].val>t[y].val)swap(x,y);
	t[x].rs=merge(t[x].rs,y);
	if(t[t[x].ls].dis<t[t[x].rs].dis)swap(t[x].ls,t[x].rs);
	t[x].dis=t[t[x].rs].dis+1;
	return x;
}
bool del[N];
int fa[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int v;
		cin>>v;
		t[i]=Node(v);
		fa[i]=i;
	}
	int m;
	cin>>m;
	while(m--)
	{
		char op;
		int x,y;
		cin>>op;
		if(op=='M')
		{
			cin>>x>>y;
			if(del[x]||del[y])continue;
			x=find(x);y=find(y);
			if(x==y)continue;
			fa[x]=fa[y]=merge(x,y);
		}
		else if(op=='K')
		{
			cin>>x;
			if(del[x])
			{
				cout<<"0"<<'\n';
				continue;
			}
			x=find(x);
			cout<<t[x].val<<'\n';
			del[x]=1;
			fa[x]=fa[t[x].ls]=fa[t[x].rs]=merge(t[x].ls,t[x].rs);
		}
	}
	return 0;
}

洛谷 P1456 Monkey King

曾经在一个森林中居住着 $N$ 只好斗的猴子。在最初他们我行我素，互不认识。但是猴子们不能避免争吵，且两只猴子只会在不认识对方时发生争吵，当争吵发生时，双方会邀请它们各自最强壮的朋友并发起决斗（决斗的为各自最强壮的朋友）。当然，在决斗之后两只猴子和他们各自的伙伴都认识对方了（成为朋友），虽然他们曾经有过冲突，但是他们之间绝不会再发生争吵了。

假设每只猴子有一个强壮值，强壮值将在一场决斗后减少为原先的一半（例如 $10$ 会减少到 $5$ ，而 $5$ 会减少到 $2$ ，即向下取整）。

我们也假设每只猴子都认识它自己（是自己的朋友）。即当他是他朋友中最强壮的，他自己就会去决斗。

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
struct Node
{
	int ls,rs,val,dis;
	Node():ls(0),rs(0),val(0),dis(-1){}
	Node(int v):ls(0),rs(0),val(v),dis(0){}
}t[N];
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(t[x].val<t[y].val)swap(x,y);
	t[x].rs=merge(t[x].rs,y);
	if(t[t[x].ls].dis<t[t[x].rs].dis)swap(t[x].ls,t[x].rs);
	t[x].dis=t[t[x].rs].dis+1;
	return x;
}
int fa[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int change(int x)
{
	int y=merge(t[x].ls,t[x].rs);
	t[x]=Node(t[x].val>>1);
	return fa[x]=fa[y]=merge(x,y);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
		{
			int v;
			cin>>v;
			t[i]=Node(v);
			fa[i]=i;
		}
		int m;
		cin>>m;
		while(m--)
		{
			int x,y;
			cin>>x>>y;
			x=find(x);y=find(y);
			if(x==y)
			{
				cout<<"-1"<<'\n';
				continue;
			}
			x=change(x);y=change(y);
			cout<<t[fa[x]=fa[y]=merge(x,y)].val<<'\n';
		}
	}
	return 0;
}

洛谷 P10641 BZOJ3252 攻略

给定一个有 $n$ 个结点的树，树有点权且点权为正整数。现选取 $k$ 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
struct Node
{
	ll ls,rs,val,dis;
	Node():ls(0),rs(0),val(0),dis(-1){}
	Node(int v):ls(0),rs(0),val(v),dis(0){}
}t[N];
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(t[x].val<t[y].val)swap(x,y);
	t[x].rs=merge(t[x].rs,y);
	if(t[t[x].ls].dis<t[t[x].rs].dis)swap(t[x].ls,t[x].rs);
	t[x].dis=t[t[x].rs].dis+1;
	return x;
}
vector<int> G[N];
int dfs(int u)
{
	int res=0;
	for(auto v:G[u])
	{
		int w=dfs(v);
		res=merge(res,(w?w:v));
	}
	if(res)t[res].val+=t[u].val;
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		int w;
		cin>>w;
		t[i]=Node(w);
	}
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
	}
	int u=dfs(1);
	ll ans=0;
	while(k--)
	{
		ans+=t[u].val;
		u=merge(t[u].ls,t[u].rs);
	}
	cout<<ans<<'\n';
	return 0;
}

参考资料​

左偏树​

pb_ds​

例题​

洛谷 P3377 【模板】左偏树/可并堆​

洛谷 P2713 罗马游戏​

洛谷 P1456 Monkey King​

洛谷 P10641 BZOJ3252 攻略​