题解 P3377 【【模板】左偏树(可并堆)】
引领天下
2019-02-24 21:09:21
折腾了几天终于把这个题A了。。。
看到手写左偏树/配对堆已经有很多题解了,而pbds却没有人介绍,我来介绍一发
首先,pbds是什么?
pbds是一个比STL还STL的库,里面封装了各种可并堆、红黑树等等数据结构,大大地方便了oier。
## 最重要的是,NOIP支持pbds了!
~~既然如此那我们当然选择封装而不是手写~~
解下来的内容大佬请略过
具体的代码里说吧
```cpp
#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!