题解 P3377 【【模板】左偏树（可并堆）】

发表于 更新于 阅读次数： Waline： 阅读次数：
P3377 【【模板】左偏树（可并堆）】题解。

折腾了几天终于把这个题A了。。。

看到手写左偏树/配对堆已经有很多题解了，而pbds却没有人介绍，我来介绍一发

首先，pbds是什么？

pbds是一个比STL还STL的库，里面封装了各种可并堆、红黑树等等数据结构，大大地方便了oier。

最重要的是，NOIP支持pbds了！

既然如此那我们当然选择封装而不是手写

解下来的内容大佬请略过

具体的代码里说吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>//引用pbds的库的堆
#pragma GCC optimize(3)
using namespace std;
inline char nc(){
  	static char buf[100000],*p1=buf,*p2=buf;
  	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template <typename _Tp>
inline void read(_Tp &x){
    int f=1;x=0;char ch=nc();
  	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
  	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=nc();}
  	x*=f;
}
inline void write(long long n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}
struct ${
    int s,id;
    inline bool operator < (const $ &p)const{if (s!=p.s)return s>p.s;else return id>p.id;}//注意！由于使用了pbds，只能重载运算符。而且pbds中的堆很毒瘤，它把<重载成>，然后排>，所以重载的时候要注意反着重载
};//结构体，存每个数的数值和id
inline $ g(int a,int b){$ p;p.s=a,p.id=b;return p;}//将2个int转成一个$
__gnu_pbds::priority_queue<$> q[100005];//定义一个pbds的堆
//使用__gnu_pbds::来引用pbds内的内容
int n,m,f[100005],x;
bool s[100005];//如果s[i]==1则i被删除
int find(int n){return f[n]==n?n:f[n]=find(f[n]);}//维护并查集，这里实际上可以路径压缩
int main(){
    read(n),read(m);
    for (int i=1;i<=n;i++)read(x),q[i].push(g(x,i)),f[i]=i;//读入的同时对每个i建一个堆，同时初始化并查集
    while (m--){
        read(x);
        if (x==1){
            int a,b;
            read(a),read(b);
            int fa=find(a),fb=find(b);
            if (fa==fb||s[a]||s[b])continue;//坑点1：注意不要把s[a]||s[b]写成了s[fa]||s[fb]
            if (q[fa].size()>q[fb].size())f[fb]=fa,q[fa].join(q[fb]);//按堆的大小合并
            else f[fa]=fb,q[fb].join(q[fa]);
        }else{
            int a;
            read(a);
            if (s[a]){puts("-1");continue;}
            int fa=find(a);
            write((q[fa].top()).s),puts(""),s[(q[fa].top()).id]=1,q[fa].pop();//同普通堆
        }
    }
}

看了一下，我的代码应该算短的。而且开了O3之后，封装的也不慢，所以向大家强烈推荐pbds！