题解 P2713 【罗马游戏】

· · 题解

加了修饰的左偏树模板题

模板题链接，双倍经验。

简简单单把左偏树模板打上就行了，注意数据范围（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;
}