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

· · 题解

题目传送门

下文中的堆皆指小根堆。

思路

核心操作：堆合并

要将以 x 为根的堆与以 y 为根的堆合并，

显然，当数据是一条链时，时间复杂度是 O(n) 的。

有两种优化方式：

本题解使用的为第二种方法。

此操作的核心代码：

int merge(int r1,int r2) {//将r1与r2合并
    if(!r1||!r2)return r1+r2;
    if(v[r1].dat>=v[r2].dat) {
        if(v[r1].key<=v[r2].key)v[r2].l=merge(r1,v[r2].l);
        else v[r2].r=merge(r1,v[r2].r);
        return r2;
    } else {
        if(v[r2].key<=v[r1].key)v[r1].l=merge(v[r1].l,r2);
        else v[r1].r=merge(v[r1].r,r2);
        return r1;
    }
}

删除

找到要删除的结点后，合并它的左右子树，然后以左右子树合并后的根替代它即可。

询问

因为我们维护的是小根堆，所以输出根结点的值就行。

赋值

将其拆分为删除+插入的操作即可。

AC code

#include<bits/stdc++.h>
using namespace std;
struct node {
    int l,r;
    long long dat,key,id;
} v[1000001];
long long a[1000001];
int n,opt,x,y,z,root[1000001],cnt,m;
bool fl;
int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int make_node(int val,int pos) {
    v[++cnt].dat=val;
    v[cnt].id=pos;
    v[cnt].key=rand();
    return cnt;
}
int merge(int r1,int r2) {
    if(!r1||!r2)return r1+r2;
    if(v[r1].dat>=v[r2].dat) {
        if(v[r1].key<=v[r2].key)v[r2].l=merge(r1,v[r2].l);
        else v[r2].r=merge(r1,v[r2].r);
        return r2;
    } else {
        if(v[r2].key<=v[r1].key)v[r1].l=merge(v[r1].l,r2);
        else v[r1].r=merge(v[r1].r,r2);
        return r1;
    }
}
void take_node(int &pos,int val,int goal) {
    if(!pos)pos=make_node(val,goal);
    else {
        if(v[pos].key%2) {
            take_node(v[pos].l,val,goal);
            if(v[v[pos].l].dat<v[pos].dat) {
                swap(v[v[pos].l].dat,v[pos].dat);
                swap(v[v[pos].l].key,v[pos].key);
                swap(v[v[pos].l].id,v[pos].id);
            }
        } else {
            take_node(v[pos].r,val,goal);
            if(v[v[pos].r].dat<v[pos].dat) {
                swap(v[v[pos].r].dat,v[pos].dat);
                swap(v[v[pos].r].key,v[pos].key);
                swap(v[v[pos].r].id,v[pos].id);
            }
        }
    }
}
void delete_node(int &pos,int goal) {
    if(!pos)return;
    if(v[pos].id==goal) {
        pos=merge(v[pos].l,v[pos].r);
        fl=true;
    } else {
        if(a[goal]>=v[v[pos].l].dat)delete_node(v[pos].l,goal);
        if(fl)return;
        if(a[goal]>=v[v[pos].r].dat)delete_node(v[pos].r,goal);
        if(fl)return;
    }
}
int main() {
    srand(time(0));
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        a[i]=read();
        root[i]=make_node(a[i],i);
    }
    for(int i=1; i<=m; i++) {
        opt=read();
        if(opt==0) {
            x=read();
            y=read();
            fl=false;
            delete_node(root[x],y);
        }
        if(opt==1) {
            x=read();
            cout<<v[root[x]].dat<<endl;
        }
        if(opt==2) {
            x=read();
            y=read();
            root[x]=merge(root[x],root[y]);
            root[y]=0;
        }
        if(opt==3) {
            x=read();
            y=read();
            z=read();
            fl=false;
            delete_node(root[x],y);
            a[y]=z;
            take_node(root[x],z,y);
        }
    }
}

record