堆

参考资料

堆简介 - OI Wiki

`std::priority_queue`

std::priority_queue<pair<int,int>> q;

`__gnu_pbds::priority_queue`

#include <bits/extc++.h>
using namespace __gnu_pbds;
__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int>>> q;

左偏树

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;
}

例题

洛谷 P3378 【模板】堆

给定一个数列，初始为空，请支持下面三种操作：

给定一个整数 $x$ ，请将 $x$ 加入到数列中。
输出数列中最小的数。
删除数列中最小的数（如果有多个数最小，只删除 $1$ 个）。

Code (1)

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	priority_queue<int> q;
	while(n--)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x;
			cin>>x;
			q.push(-x);
		}
		else if(op==2)
		{
			cout<<-q.top()<<'\n';
		}
		else if(op==3)
		{
			q.pop();
		}
	}
	return 0;
}

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

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

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

Code (2)

PBDS
左偏树

#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;
}

#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;
}

洛谷 P11266 【模板】可并堆 2

给定正整数 $n$ 和 $m$ 以及一个长为 $n$ 的整数序列 $a_{1,\dots,n}$ 。

你需要维护序列 $a_{1,\dots,n}$ 以及 $n$ 个集合 $S_{1,\dots,n}$ ，初始时 $S_i=\{i\}$ 。

接下来要进行以下四种操作共 $m$ 次，每次操作形如：

0 x y：表示将元素 $y$ 从集合 $S_x$ 中删去。保证此时元素 $y$ 在集合 $S_x$ 中。
1 x：表示询问 $\min_{i\in S_x} a_i$ ，保证此时集合 $S_x$ 非空。
2 x y：将集合 $S_y$ 中并入 $S_x$ 并清空集合 $S_y$ 。保证此时集合 $S_x,S_y$ 均非空，且此次操作后不会再出现涉及集合 $S_y$ 的操作。
3 x y z：表示将 $a_y$ 赋值为 $z$ 。保证此时元素 $y$ 在集合 $S_x$ 中，且 $z<a_y$ 。

不难发现这是一道堆的模板题，所以现在请你完成它。

Solution

参考资料

堆 - OI Wiki

解题思路

说明

本题使用 GNU PBDS（Policy-Based Data Structures）可以优雅地解决。

__gnu_pbds::priority_queue 相比标准库的 std::priority_queue 提供了更灵活的修改和删除操作。

函数

__gnu_pbds::priority_queue 支持以下函数：

push(x)：向堆中压入元素 x，返回该元素位置的迭代器。
erase(it)：把迭代器 it 位置的键值从堆中擦除。
top()：返回堆顶元素。
join(x)：把堆 x 合并到 *this 并把 x 清空。
modify(it,x)：把迭代器 it 位置的键值修改为 x，并对底层储存结构进行排序。

实现

初始时，将每个数 $a_i$ 压入堆 $q_i$ ，并记录其迭代器的位置 $it_i$ 。

对于每次操作：

0 x y：使用 erase(it) 在 $q_x$ 删除 $it_y$ 位置的键值。
1 x：使用 top() 查询 $q_x$ 堆顶元素（即最小值）。
2 x y：使用 join(x) 把 $q_x$ 合并到 $q_y$ 并把 $q_x$ 清空。
3 x y z：使用 modify(it,x) 把 $q_x$ 中 $it_y$ 位置的键值修改为 $x$ 。

代码非常简洁，缺点是常数较大。

参考代码

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

const int N=1000005;
__gnu_pbds::priority_queue<int,greater<int>> q[N];
__gnu_pbds::priority_queue<int,greater<int>>::point_iterator it[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){int x;cin>>x;it[i]=q[i].push(x);}
	while(m--)
	{
		int op,x,y,z;
		cin>>op;
		if(op==0){cin>>x>>y;q[x].erase(it[y]);}
		else if(op==1){cin>>x;cout<<q[x].top()<<'\n';}
		else if(op==2){cin>>x>>y;q[x].join(q[y]);}
		else if(op==3){cin>>x>>y>>z;q[x].modify(it[y],z);}
	}
	return 0;
}

洛谷 P2713 罗马游戏

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

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

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

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

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

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

Code (1)

#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$ ，即向下取整）。

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

Code (1)

#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$ 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。

Code (1)

#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;
}

参考资料​

std::priority_queue​

__gnu_pbds::priority_queue​

左偏树​

例题​

洛谷 P3378 【模板】堆​

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

洛谷 P11266 【模板】可并堆 2​

参考资料​

解题思路​

说明​

函数​

实现​

参考代码​

洛谷 P2713 罗马游戏​

洛谷 P1456 Monkey King​

洛谷 P10641 BZOJ3252 攻略​

参考资料

`std::priority_queue`

`__gnu_pbds::priority_queue`

左偏树

例题

洛谷 P3378 【模板】堆

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

洛谷 P11266 【模板】可并堆 2

参考资料

解题思路

说明

函数

实现

参考代码

洛谷 P2713 罗马游戏

洛谷 P1456 Monkey King

洛谷 P10641 BZOJ3252 攻略