可并堆有一种黑科技是用线段树合并实现，还能可持久化，时间复杂度nlogn。

这里介绍左偏树。

d值表示走右边到叶子的距离。满足d[r] <= d[l]

写法上用rt维护根节点，类似线段树。

不要把两个merge写混淆了！

放一个模板。

namespace lt {    int ls[N], rs[N], siz[N], d[N], rt[N];    LL val[N], sum[N];    int merge(int x, int y) {        if(!x || !y) return x | y;        if(val[x] < val[y]) std::swap(x, y);        rs[x] = merge(rs[x], y);        if(d[rs[x]] > d[ls[x]]) std::swap(ls[x], rs[x]);        d[x] = d[rs[x]] + 1;        sum[x] = sum[ls[x]] + sum[rs[x]] + val[x];        siz[x] = siz[ls[x]] + siz[rs[x]] + 1;        return x;    }    inline void exmerge(int x, int y) { // y -> x        rt[x] = merge(rt[x], rt[y]);        return;    }    inline void pop(int x) {        rt[x] = merge(ls[rt[x]], rs[rt[x]]);        return;    }    inline int getSum(int x) {        return sum[rt[x]];    }    inline int getSiz(int x) {        return siz[rt[x]];    }    inline void init(int i, LL v) {        val[i] = v;        sum[i] = v;        siz[i] = 1;        d[i] = 1;        rt[i] = i;        return;    }}

模板。

额外用一个并查集维护每个人在左偏树中的编号。

洛谷P4331 数字序列 主要是想到那个毒瘤合并的结论...