题解：P11266 【模板】完全体·堆

题目链接

• 洛谷 P11266 【模板】完全体·堆

解题思路

看了题解区，竟然没有人写可爱的左偏树。

我们需要支持四种操作：

1. 删除集合中的元素。
2. 取集合中的最小值。
3. 合并两个集合。
4. 修改集合中的元素。

那么我们可以用常数极小的左偏树（可并堆） 来解决这道模板题。

对于左偏树的基础操作，详见左偏树-OI Wiki或洛谷 P3377【模板】左偏树/可并堆。

在支持删除元素的情况下，我们在进行 push_up 操作时需要查找节点 x 的父节点，因此无法使用路径压缩来查找左偏树的根节点。如果直接向上查找根节点，会导致 TLE。

为了解决这个问题，我们可以引入一个 root 数组，其中 root_x 存储集合 S_x 的根节点下标。在每次执行 merge、erase 和 push_up 操作时，对 root 数组进行相应的更新。

在删除操作中，可以直接将元素 x 从左偏树中删除，然后重新初始化元素 x，将其作为一个独立的左偏树，再将其合并回原来的左偏树，保证了堆的性质。

此外，对于修改操作，还有另一种更高效的处理方式。由于题目保证 z<a_y，我们可以在修改 x 的权值后与其父节点进行比较。如果 x 的父节点的权值大于 x 的权值，则交换 x 和其父节点的位置。这样常数极小但是我写挂了。

整体时间复杂度为 O(m\log{n})。跑得飞快，仅仅跑了 508 ms 。

以下是使用朴素修改操作的左偏树 AC 代码的提交记录。

参考代码

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
    template<typename T> inline T read(T& x)
    {
        char ch=getchar();bool f=true;x=0;
        while(ch<'0'||ch>'9') f&=(bool)(ch^'-'),ch=getchar();
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        return x=f?x:-x;
    }
    template<typename T,typename... Args> inline void read(T& x,Args&... args){read(x);read(args...);}
    template<typename T> void print(const T x){if(x<0){putchar('-');print(-x);return ;}if(x>9) print(x/10);putchar(x%10^48);}
    template<typename T> void print(const T x,const char ch){print(x);putchar(ch);}
}using namespace IO;
typedef long long ll;

const int N=1e6+5;
int n,m;

int root[N];
struct ZPS{int ls,rs,dis,fa;ll val;}tree[N];
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
int merge(int x,int y)
{
    if(!x||!y) return x|y;
    if(tree[x].val>tree[y].val||(tree[x].val==tree[y].val&&x>y)) swap(x,y);
    rs(x)=merge(rs(x),y);
    if(tree[ls(x)].dis<tree[rs(x)].dis) swap(ls(x),rs(x));
    tree[x].dis=tree[rs(x)].dis+1;
    return tree[ls(x)].fa=tree[rs(x)].fa=tree[x].fa=x;
}
void push_up(const int x)
{
    if(!x) return ;
    if(tree[ls(x)].dis<tree[rs(x)].dis) swap(ls(x),rs(x));
    if(tree[x].dis^(tree[ls(x)].dis+1))
        tree[x].dis=tree[ls(x)].dis+1,push_up(tree[x].fa);
}
inline int erase(const int x,const int pos)
{
    int y=merge(ls(x),rs(x));
    if(tree[x].fa^x)
    {
        tree[y].fa=tree[x].fa;
        if(ls(tree[y].fa)==x) ls(tree[y].fa)=y;
        if(rs(tree[y].fa)==x) rs(tree[y].fa)=y;
        push_up(tree[y].fa);
    }else root[pos]=tree[y].fa=y;
    tree[x].fa=y;ls(x)=rs(x)=0;
    return pos;
}
inline ll top(const int pos){return tree[root[pos]].val;}
inline void modify(const int x,const int k,const int pos)
{
    erase(x,pos);
    tree[x]={0,0,1,x,k};
    root[pos]=merge(root[pos],x);
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("awa.in","r",stdin);
    freopen("awa.out","w",stdout);
    #endif

    read(n,m);
    for(int i=1;i<=n;++i) read(tree[i].val),tree[i].dis=1,tree[i].fa=root[i]=i;

    int opt;ll x,y,z;
    while(m--)
        switch(read(opt))
        {
            case 0:read(x,y),erase(y,x);break;
            case 1:read(x),print(top(x),'\n');break;
            case 2:read(x,y),root[x]=merge(root[x],root[y]);break;
            case 3:read(x,y,z),modify(y,z,x);break;
        }

    return 0;
}