自动搬运

查看原文

来自洛谷，原作者为

	vеctorwyx 面壁十年图破壁，难酬蹈海亦英雄

搬运于2025-08-24 21:40:44，当前版本为作者最后更新于2020-03-04 21:58:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

加了修饰的左偏树模板题

模板题链接，双倍经验。

简简单单把左偏树模板打上就行了，注意数据范围（n<=1e6,m<=1e5）。

以上为扯淡内容，正文开始。

题意（翻译成术语）：

对n个小根堆做m个操作：

M （x，y）合并x所在堆和y所在堆（如果x或y被删除则忽略次操作）；

K（x）输出x所在堆的堆顶元素并将其删除，如果x已经被删除这输出0 ；

百度百科：左偏树。

外节点：没有左子树或没有右子树的节点；

点的距离：点到它后代中离它最近的外节点经过的边数；

合并方法（小根堆）：

设要将堆顶元素为 Y 的堆并入堆顶元素为 X 的堆（谁并入谁无所谓，这里是为了便于解释），则将X与Y比较，如果X>Y就交换X与Y，将Y继续与X的右子节点比较（递推）。

同时左偏树要保证往左偏，即保证左子节点的距离要比右子节点的距离要大。

删除最小的点（堆顶元素）的方法：

标记堆顶元素已删除，合并其左子树和右子树；

话不多说，上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,a[1000010],d[1000010],ls[1000010],rs[1000010],f[1000010],x,y;//a是每个节点的值，d是节点的距离，ls左子节点，rs右子节点，f父节点（并查集）
bool b[1000010];//是否已经删除
char z;
int find(int x)
{
	if(f[x]==x)
	return x;
	return f[x]=find(f[x]);
}//并查集
int merge(int x,int y)//合并（返回当前节点的值）
{
	if(!x||!y)//有一棵树已经空了
	return x+y;//返回
	if(a[x]>a[y]||(a[x]==a[y]&&x>y))//交换条件
	swap(x,y);
	rs[x]=merge(rs[x],y);//右子节点
	if(d[ls[x]]<d[rs[x]])//如果左子节点距离小于右子节点
	swap(ls[x],rs[x]);//交换左右子树
	d[x]=d[rs[x]]+1;//算出当前点的距离
	return x;
}
int main()
{
	cin>>n;
	d[0]=-1;
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
		cin>>a[i];
	}
	cin>>m; 
	while(m--)
	{
		cin>>z;
		if(z=='M')
		{
			cin>>x>>y;
			if(b[x]||b[y])
			continue;//有一个点已经被删除了
			x=find(x);
			y=find(y);
			if(x==y)//已经在同一个堆中了
			continue;
			f[x]=f[y]=merge(x,y);
		}
		else if(z=='K')
		{
			cin>>x;
			if(b[x])//已经删除
			{
				cout<<0<<endl;
				continue;
			}
			x=find(x);
			cout<<a[x]<<endl;
			b[x]=1;//标记删除
			f[x]=f[ls[x]]=f[rs[x]]=merge(ls[x],rs[x]);//合并左右子树
			ls[x]=rs[x]=d[x]=0;
		}
	}
	return 0;
}