题解 P3377 【【模板】左偏树(可并堆)】

引领天下

2019-02-24 21:09:21

Solution

折腾了几天终于把这个题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!