左偏树
基础定义
外节点：子节点数小于两个的节点。
一个节点的 ：其到子树中最近的外节点所经过的边的数量。空节点的 dist 为 。
左偏树是一棵二叉树，它不仅具有堆的性质，并且是「左偏」的：每个节点左儿子的 都大于等于右儿子的 。
注意这不是深度，所以左偏树的深度没有限制。
因此，。
操作
合并
以小根堆为例。
合并两个堆的时候，我们把根节点设成权值更小的点，然后将另一棵树和自己的右子树递归合并。最后如果不满足左偏性质就交换左右儿子。
至于时间复杂度，跟深度有关，而 是 级别的，所以复杂度正确。
int merge(int x,int y){
if(!x||!y)return x+y;
if(t[x].v>t[y].v)swap(x,y);
rs(x)=merge(rs(x),y);
t[rs(x)].f=x;
if(t[ls(x)].d<t[rs(x)].d)swap(ls(x),rs(x));
t[x].d=t[rs(x)].d+1;
return x;
}
查询
路径压缩可以查询到对顶，还是很简单的。
插入
就是普通堆的插入。
建堆
每次把队首的两个堆取出来，合并后扔到队尾，直到只剩下一个堆。
删除任意节点
先将左右儿子合并，然后自底向上更新 、不满足左偏性质时交换左右儿子，当 无需更新时结束递归。
void pushup(int x){
if(!x)return;
if(t[x].d!=t[rs(x)].d+1){
t[x].d=t[rs(x)].d+1;
pushup(t[x].f);
}
}
void pop(int x,int y){
int fa=t[y].f,root=merge(ls(y),rs(y));
if(!fa){
rt[x]=root;
t[root].f=0;
return;
}
if(ls(fa)==y)ls(fa)=root;
else rs(fa)=root;
t[root].f=fa;
pushup(root);
return;
}
我的错误
删除 的时候， 也需要赋值成为 merge(ls(x),rs(x))，因为有的点指向了它。
还有，如果两个点本来就在一个堆里面就不要合并了。
最 好 的写法
老朋友了，考场写起来是真的快。
#include<bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
int n,m;
__gnu_pbds::priority_queue<int,greater<int>>q[1000010];
__gnu_pbds::priority_queue<int,greater<int>>::point_iterator p[1000010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
p[i]=q[i].push(x);
}
for(int i=1;i<=m;i++){
int op,x,y,z;
cin>>op;
if(op==0){cin>>x>>y;q[x].erase(p[y]);};
if(op==1){cin>>x;cout<<q[x].top()<<'\n';};
if(op==2){cin>>x>>y;q[x].join(q[y]);};
if(op==3){cin>>x>>y>>z;q[x].modify(p[y],z);};
}
return 0;
}
P1552 [APIO2012] 派遣
这个就直接维护每个点薪水最小的那些人就行了，一点点合并上去。
P3642 [APIO2016] 烟花表演
P4331 [BalticOI 2004] Sequence (Day1)
P4331 [BalticOI 2004] Sequence (Day1)。
将单调递增转化成单调不降的技巧：数组所有元素减去下标。
首先我们先找找这道题的性质。
我们发现，如果这个序列是单调递增的，我们只需要 ，如果是单调递减，就取中位数就行了。
所以我们考虑能不能将序列拆成一段一段的。
如果这一段是单调递增的，就先不管，如果是单调递减的，我们考虑全选中位数，然后合并成一个集合。
然后相邻的集合如果左边的中位数小于右边的就不用管，否则合并两个集合的数来求新的中位数，成为新的集合。
重复这个过程就行了，中位数用可并堆求。
我们用可并堆，然后只需要保留 个最小的节点，此时堆顶就是中位数。
因为我们保证了 ，所以新加入的所有元素只可能更小，所以其余大的那一部分可以直接删掉，不会影响答案。复杂度正确。
注意，我们需要用大根堆。
P3273 [SCOI2011] 棘手的操作
题解还是太强了，pbds + 启发式合并堆竟然还是 的。因为 pbds 的插入是 的。
甚至 pbds 支持：for(int i:q[y])！
思路
这道题我们发现最难办的是对于块的合并时，块的整体 pbds 难以维护。
所以我们干脆就用优先队列（pbds O(1) insert），自己启发式合并就行了。
然后至于块 对全局的贡献，我们只需要记录最大值的就行了，放进全局的堆中。然后还需要记录每个数的值，修改的时候直接修改，然后也需要放进全局的堆中。
其他操作就很简单了。