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

Lysra · 2024-11-08 17:45:15 · 题解

大家好，我非常喜欢平衡树，所以我就用 STL 过了本题。

set 的前置芝士：

• 合并：x.insert(y.begin(),y.end())。

• 二分查找（返回指针）：x.lower_bound(y)。

接下来我们考虑实现题目操作。

先考虑最简单的 2 操作和 3 操作，直接暴力合并、二分查找后删除即可。

再考虑如何快速实现 0 操作，这里要用到懒惰删除的思想。当需要删除一个数时，可以先标记这个数，然后在输出前判断最小值是否被标记过即可。

总体时间复杂度 O(n\log_2n)。

代码：

#include<bits/stdc++.h>
#define N 1000005
#define int long long
#define INF 1e18
#define val first
#define id second
namespace IO{
    template<typename T> inline void write(T x){
        if(x<0) putchar('-'),x=-x;
        if(x==0){
            putchar('0'); return ;
        }
        if(x>9) write(x/10);
        putchar(x%10+'0');
        return ;
    }
    template<typename T> inline void read(T &x){
        x=0; int w=1; char ch=getchar();
        while(!isdigit(ch)){
            if(ch=='-') w=-1; ch=getchar();
        }
        while(isdigit(ch))
            x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x*=w; return ;
    }
}
using namespace IO;
using namespace std;
int n,m,e[N],a[N];
set<pair<int,int> >s[N];
signed main(){
    read(n),read(m);
    for(int i=1;i<=n;i++){
        read(a[i]);
        s[i].insert({a[i],i});
    }
    int op,x,y,z;
    while(m--){
        read(op),read(x);
        if(op==0) read(y),e[y]=1;
        if(op==1){
            while(!s[x].empty()&&e[s[x].begin()->id]) s[x].erase(s[x].begin());
            write(s[x].begin()->val),putchar('\n');
        }
        if(op==2){
            read(y);
            s[x].insert(s[y].begin(),s[y].end());
        }
        if(op==3){
            read(y),read(z);
            auto it=s[x].lower_bound({a[y],y});
            s[x].erase(it),s[x].insert({z,y});
            a[y]=z;
        } 
    }
    return 0;
}