配对堆学习笔记
可并堆，比较好写，不能持久化。
结构是一个儿子指针一个兄弟指针，根链式前向星差不多。合并就直接把大的堆作为小的堆的儿子，删除就两两配对暴力合并儿子，这样好像可以让之后儿子数量少一点。具体的要用势能分析我也不会/kk
例题：P3377
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
int x=0,pos=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return pos?x:-x;
}
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N = 1e5+200;
int f[N];
int gf(int x){
if(f[x]==x) return x;
else return f[x]=gf(f[x]);
}
int nex[N],son[N];int cnt;ll val[N];
void add(int u,int v){ //v作为u的儿子
nex[v]=son[u];son[u]=v;
}
int merge(int u,int v){//小根堆
if(!u||!v) return u^v;
if(val[u]>val[v]||(val[u]==val[v]&&u>v)) swap(u,v);add(u,v);return u;
}
int merges(int u){//把u和u的兄弟两两配对，merge到一起
if(!u) return 0; if(!nex[u]) return u;
int v1=nex[u],v2=nex[v1];
nex[u]=nex[v1]=0;return merge(merge(u,v1),merges(v2));
}
/*
void dfs(int u){
ans[++top]=val[u];
for(int i=son[u];i;i=nex[i]) dfs(i);
}*/
struct heap{
int rt;
void push(ll x){val[++cnt]=x;rt=merge(rt,cnt);}
ll top(){return val[rt];}
void pop(){rt=merges(son[rt]);}
void join(int now){rt=merge(rt,now);}
}h[N];
int main(){
int n=read(),m=read();
FOR(i,1,n){
int x=read();f[i]=i;h[i].push(x);
}
FOR(i,1,m){
int opt=read();
if(opt==1){
int x=read(),y=read();int fu=gf(x),fv=gf(y);
if(val[x]==-1||val[y]==-1||fu==fv) continue;
f[fv]=fu;
h[fu].join(h[fv].rt);
}else{
int x=read();
if(val[x]==-1) printf("-1
");
else{
int fu=gf(x);printf("%d
",h[fu].top());val[h[fu].rt]=-1;h[fu].pop();
}
}
}
return 0;
}
例题 洛谷P3642 [APIO2016]烟火表演
这题是维护凸包并，平移线段（插入拐点），弹出右端的一些线段
由于斜率有规律，我们直接用可并堆维护拐点即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
int x=0,pos=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return pos?x:-x;
}
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;--i)
const int N = 6e6+200;
int f[N];
int gf(int x){
if(f[x]==x) return x;
else return f[x]=gf(f[x]);
}
int nex[N],son[N],d[N];int cnt;ll val[N],w[N];
void add(int u,int v){ //v作为u的儿子
nex[v]=son[u];son[u]=v;
}
int merge(int u,int v){//大根堆
if(!u||!v) return u^v;
if(val[u]<val[v]) swap(u,v);add(u,v);return u;
}
int merges(int u){//把u和u的兄弟两两配对，merge到一起
if(!u) return 0; if(!nex[u]) return u;
int v1=nex[u],v2=nex[v1];
nex[u]=nex[v1]=0;return merge(merge(u,v1),merges(v2));
}
ll ans[N],top=0;
void dfs(int u){
ans[++top]=val[u];
for(int i=son[u];i;i=nex[i]) dfs(i);
}
struct heap{
int rt;
void push(ll x){val[++cnt]=x;rt=merge(rt,cnt);}
ll top(){return val[rt];}
void pop(){rt=merges(son[rt]);}
void join(int now){rt=merge(rt,now);}
}h[N];
int main(){
int n=read(),m=read();
ll s0=0;
FOR(i,2,n+m){
f[i]=read(),w[i]=read();d[f[i]]++;s0+=w[i];
}
ROF(i,n+m,2){
ll l=0,r=0;
while(d[i]){
d[i]--;r=h[i].top();h[i].pop();
}l=h[i].top();h[i].pop();
h[i].push(l+w[i]);h[i].push(r+w[i]);
h[f[i]].join(h[i].rt);
}
dfs(h[1].rt);
sort(ans+1,ans+top+1);top-=d[1];
FOR(i,0,top-1){
s0-=1ll*(top-i)*(ans[i+1]-ans[i]);
}
printf("%lld
",s0);
return 0;
}