详解左偏树(可并堆)的代码和示例题目

算法能解决的问题

它主要解决的是可并堆(Mergeable Heap)的问题, 如果问题是要取最值并且还要合并堆, 适合用左偏树计算

数据结构的操作

• 插入一个数, $O(\log n)$
• 求最小值, $O(1)$
• 删除最小值, $O(1)$
• *合并两个左偏树, $O(\log n)$

左偏树记录的信息

以小根堆为例

• 当前节点的权值$v$
• $dis$表示距离最近空节点的距离, 并且对于每棵子树左儿子的距离大于等于右儿子的距离
  

形式化表示为$ls.dis\ge rs.dis$

$n$个节点的左偏树最坏情况下高度是$\log n$

核心函数
merge(a, b)合并$a,b$两棵子树并且返回合并后的根节点

假设合并$a,b$两棵子树, 并且$a.v\le b.v$, 左边子树的权值$\ge a$, 右边子树的权值$\ge b$

尝试将$b$和$a$的右子树进行合并, 是递归的过程
如果发现右边子树的$dis$大于了左边的$dis$, 交换两棵子树

(1) 插入一个数

• 建立只有一个点的左偏树
• 将这个点与原树合并

(2) 删除根节点

• 首先先删除掉根节点
• 合并两棵左右子树

(3) 获得最小值
直接返回左偏树根节点的值

示例代码

并查集维护哪些点在一个集合中, 用左偏树的根节点作为并查集的代表元素

比较复杂的操作是从集合中删除一个点, 对于左偏树来说假设根节点的左右儿子是$a,b$, 删除根节点后, 合并$a,b$两棵树

但是, 并查集没办法删除点, 需要做如下操作
不妨设新的左偏树根节点是$a$, 在并查集中找到对应的位置$p$, 将并查集的代表元素与$p$交换

并查集的换根操作, 这样就可以维护这样的集合

核心代码
始终将节点值较大的合并到节点值较小的, 也就是交换后的$x$是被合并的新的根, 然后将$rs[x]$也就是$x$的右子树和$y$树进行合并

int merge(int x, int y) {
   
    if (!x || !y) return x + y;
    if (cmp(y, x)) swap(x, y);
    rs[x] = merge(rs[x], y);
    if (dis[rs[x]] > dis[ls[x]]) swap(ls[x], rs[x]);
    dis[x] = dis[rs[x]] + 1;
    return x;
}

示例代码

对于左偏树来说假设左儿子$ls$或者右儿子$rs$为空, 那就是节点$0$, 但是数据范围是$[1,10^9]$, $0$小于任意一个数, $0$会作为根节点, 但是$0$不能作为根节点因为数值$0$不存在

因此需要初始化$v[0]=+\infty$

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n;
int v[N], dis[N], ls[N], rs[N];
int p[N], idx;

int find(int x) {
   
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

bool cmp(int a, int b) {
   
    if (v[a] != v[b]) return v[a] < v[b];
    return a < b;
}

int merge(int x, int y) {
   
    if (!x || !y) return x + y;
    if (cmp(y, x)) swap(x, y);
    rs[x] = merge(rs[x], y);
    if (dis[rs[x]] > dis[ls[x]]) swap(ls[x], rs[x]);
    dis[x] = dis[rs[x]] + 1;
    return x;
}

void insert(int x) {
   
    v[++idx] = x;
    p[idx] = idx;
    dis[idx] = 1;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 初始化不存在节点
    v[0] = 2e9;

    cin >> n;
    while (n--) {
   
        int op;
        cin >> op;
        if (op == 1) {
   
            int x;
            cin >> x;
            insert(x);
         }
        else if (op == 2) {
   
            int x, y;
            cin >> x >> y;
            x = find(x), y = find(y);
            if (x != y) {
   
                if (cmp(y, x)) swap(x, y);
                p[y] = x;
                merge(x, y);
            }
        }
        else if (op == 3) {
   
            int x;
            cin >> x;
            cout << v[find(x)] << '\n';
        }
        else {
   
            int x;
            cin >> x;
            x = find(x);
            if (cmp(rs[x], ls[x])) swap(ls[x], rs[x]);
            // 并查集换根
            p[x] = ls[x], p[ls[x]] = ls[x];
            merge(ls[x], rs[x]);
        }
    }

    return 0;
}

*数字序列

将问题转化为非下降子序列
原数列$a_i$, 希望求的数列是$b_i$
现在做如下变化, 将$a_i^{\prime }=a_i-i$, 使得$b_i^{\prime }=b_i-i$

因为$b_i-b_{i-1}\ge 1$, 我们希望的是$b_i^{\prime }-b_{i-1}^{\prime }\ge 0$, 因此

$$b_i-b_{i-1}^{\prime }-1\ge 0$$
也就是
$$(b_i-i)-(b_{i-1}-(i-1))\ge 0$$

这样变换之后就有$b_1^{\prime }\le b_2^{\prime }\le ...\le b_n^{\prime }$

转换之前结果是
$$\sum \left|a_i-b_i\right|$$
转化之后的结果也是这个, 因此问题可以合法的转化过来

从递增序列转化为非下降序列

现在令$a_i=a_i^{\prime },b_i=b_i^{\prime }$

将$a_i$序列分为两段, 假设最优解的$b_i$取相同值, 类似于货仓选择问题(数轴上有一些位置, 选择一个位置使得到其他位置的距离之和最短, 位置就是中位数位置)

假设前一段$b_1=b_2=...=b_n=u$, 后一段最优解$b_{n+1}=b_{n+1}=...=b_m=v$

因为要求所有$b_i$相等, $u$就是第一段中位数, 同理$v$是第二段中位数

$(1)$ $u\le v$

那么前半段取$u$, 后半段取$v$就是最优解, 假设前一段最优解是$A$, 后一段最优解是$B$, 那么最优解的下界是$A+B$, 因为$u,v$保持非下降, 可以取到下界, 因此$u,v$就是整体最优解

$(2)$ $u>v$

这种情况最优解是两段的中位数(红色线)

猜想(1): 最优解的情况$b_n\le u$并且$b_{n+1}\ge v$

证明猜想(1): 超过$u$的部分可以变为$u$, 并且结果不会变差, $v$部分同理

因为前后两段是对称的, 先将后半段取出

证明: 将虚线部分替换最优解结果不会变差

假设给定的解$b_i$有$k$段

假设后面的值是$b_i=w>v$, 意味着后半段最优解不取$v$应该取$w$会变得更好, 因此后面一段的中位数$\le v$

意味着红色框住的部分至少有一半的数$\le v$, 向下移动$x$, 也就是$b_i-x$, 拉近了$|b_i-a_i|$的值, 使得$a_i$与$b_i$更近了

但是对于另一半来说变化值一定在$[-x,x]$之间, 最坏情况每个数字$+x$, 但是至少有一半的数字$-x$了, 结果不会变差

但是操作的影响是将第二段移动到了第一段的位置, 少了一段

这样操作后, 最终就剩一段, 值为$b_1$

猜想(2): 选择虚线部分$[v,b_1]$, 结果不会更差

答案等于
$$
|a_{\frac{n}{2}} - x| + |a_{\frac{n}{2} + 1} - x|

• |a_{\frac{n}{2} - 1} - x| + |a_{\frac{n}{2} + 2} - x| + …
  $$
  证明猜想(2): 一共$\frac{n}{2}$对数, $x$靠近中位数$v$对答案没影响

结论是将$b_i$替换为$[b_1,n]$的任意数, 结果不会变差

假设前面已经维护了最优解, 对于当前新加入的位置看作是一段, 如果是单调上升的不需要处理

合并两段, 如果发现新合并的中位数还是低于前面的段, 那么继续合并

合并结束后, 一定是递增的段, 每一段的最优解是$X_0,X_1,...,X_k$, 那么整体的最优解就是$X_0+X_1+...+X_k$

合并中位数的过程可以使用左偏树维护, 较少一半数的最大值就是中位数

合并两段, 中位数一定在这两段之间, 如果合并后的中位数是上半段被左偏树维护就是正确的, 但是如果是下半段不在左偏树中得到的中位数就是错误的!

但是, 在当前问题中是左偏树是可以维护两段的中位数的, 分为两种情况

• 当前合并的线段只有一个数字

不会产生错误的情况

• 当前合并的是一段数

因为插入一个数最多只会在原中位数左右一个位置处发生变化

也就是说新的中位数和原中位数之间是空的, 不会产生错误的情况

因此, 才可以使用左偏树维护中位数的情况

示例代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e6 + 10;

int n;
int v[N], dis[N], ls[N], rs[N];
struct Seg {
   
    int ed, root, sz;
} stk[N];
int ans[N];

int merge(int x, int y) {
   
    if (!x || !y) return x + y;
    if (v[y] > v[x]) swap(x, y);
    rs[x] = merge(rs[x], y);
    if (dis[rs[x]] > dis[ls[x]]) swap(ls[x], rs[x]);
    dis[x] = dis[rs[x]] + 1;
    return x;
}

int pop(int x) {
   
    return merge(ls[x], rs[x]);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n;  ++i) {
   
        cin >> v[i];
        v[i] -= i;
    }

    int t = 0;
    for (int i = 1; i <= n; ++i) {
   
        Seg cur = {
   i, i, 1};
        dis[i] = 1;

        while (t && v[cur.root] < v[stk[t].root]) {
   
            cur.root = merge(cur.root, stk[t].root);
            if (cur.sz & 1 && stk[t].sz & 1) cur.root = pop(cur.root);
            cur.sz += stk[t].sz;
            t--;
        }
        stk[++t] = cur;
    }

    // 计算每一段中位数
    for (int i = 1, j = 1; i <= t; ++i) {
   
        while (j <= stk[i].ed) ans[j++] = v[stk[i].root];
    }

    LL res = 0;
    for (int i = 1; i <= n; ++i) res += abs(ans[i] - v[i]);
    cout << res << '\n';
    for (int i = 1; i <= n; ++i) cout << ans[i] + i << ' ';
    cout << '\n';

    return 0;
}

*K单调

分解为$k$个不相交相邻的的单调序列, 问最小代价

一般来说分解 + 计算极值, 尝试用动态规划解决

数据范围最大$1000$, 可以预处理$cost(i,j)$, 代表将$[i,j]$这一段变为单调序列的最小代价, 暴力预处理$O(n^2\log n)$

定义状态表示$f(i,j)$表示从$1\sim a_i$变为$k$段单调序列的最小代价

状态转移看最后位置不同点, 因为分为了$j$段, 按照最后一段长度能从什么位置转移过来, 形式化的表示为

$$f(i,j)=\min (f(i,j),f(i-k,j-1)+cost(i-k+1,i))$$

但是因为每一段区间可以单调上升也可以单调下降, 需要处理单调下降的情况

示例代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 12;

int n, m;
int f[N][M], cost[N][N];
int a[N], v[N], dis[N], ls[N], rs[N];
struct Seg {
   
    int root;
    int tot_sz, tot_sum;
    int tr_sz, tr_sum;

    int calc_cost() const {
   
        int mid = v[root];
        return mid * tr_sz - tr_sum + tot_sum - tr_sum - (tot_sz - tr_sz) * mid;
    }
} stk[N];

int merge(int x, int y) {
   
    if (!x || !y) return x + y;
    if (v[y] > v[x]) swap(x, y);
    rs[x] = merge(rs[x], y);
    if (dis[rs[x]] > dis[ls[x]]) swap(ls[x], rs[x]);
    dis[x] = dis[rs[x]] + 1;
    return x;
}

int pop(int x) {
   
    return merge(ls[x], rs[x]);
}

void get_cost(int u) {
   
    int t = 0, ans = 0;
    for (int i = u; i <= n; ++i) {
   
        Seg cur = {
   i, 1, v[i], 1, v[i]};
        ls[i] = rs[i] = 0, dis[i] = 1;

        while (t && v[cur.root] < v[stk[t].root]) {
   
            ans -= stk[t].calc_cost();
            cur.root = merge(cur.root, stk[t].root);
            // 两段是奇数需要将cur段的中位数弹出
            bool flag = cur.tot_sz & 1 && stk[t].tot_sz & 1;
            cur.tot_sz += stk[t].tot_sz;
            cur.tot_sum += stk[t].tot_sum;
            cur.tr_sz += stk[t].tr_sz;
            cur.tr_sum += stk[t].tr_sum;
            if (flag) {
   
                cur.tr_sz--;
                cur.tr_sum -= v[cur.root];
                cur.root = pop(cur.root);
            }
            t--;
        }
        stk[++t] = cur;
        ans += cur.calc_cost();
        cost[u][i] = min(cost[u][i], ans);
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    memset(cost, 0x3f, sizeof cost);
    for (int i = 1; i <= n; ++i) v[i] = a[i] - i;
    for (int i = 1; i <= n; ++i) get_cost(i);
    for (int i = 1; i <= n; ++i) v[i] = -a[i] - i;
    for (int i = 1; i <= n; ++i) get_cost(i);

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            for (int k = 1; k <= i; ++k) {
   
                f[i][j] = min(f[i][j], f[i - k][j - 1] + cost[i - k + 1][i]);
            }
        }
    }

    cout << f[n][m] << '\n';
    return 0;
}