mydcwfy's Blog

左偏树

Posted on
Symbols count in article: 4k Reading time ≈ 9 mins.

又叫可合并堆。

左偏树

1. 本质与基本功能

左偏树本质是堆。

支持功能：

  1. 插入一个数 $O(\log n)$
  2. 求最小值 $O(1)$
  3. 删除最小值 $O(\log n)$
  4. 合并两棵左偏树 $O(\log n)$

2. 维护信息

  1. 值 val
  2. 到最近空节点的距离 dis

左偏树必须满足：$dis(leftchild) \geq dis(rightchild)$

下面我们证明这样一个性质：

这个等价于 $f(k)=2^k-1$，其中 $f(k)$ 表示当根节点的距离为 k 时，包含的最少节点个数。

可以使用数学归纳法。

对于 $k=1,f(k)-2^k-1$。

$f(k)=f(k’)+(2^{k-1}+1)(k’\geq k-1)$，其中 $f (k’)$ 是左子树的最少节点个数。

可以发现 f 函数是单调递增的，则 $f(k’)\geq f(k-1)=2^{k-1}+1$，带入原式即可。

3. 特殊函数——merge

由于前 3 个操作都比较简单，且是堆的基本操作，所以只讲最后一个。

$\operatorname{merge}(x,y)$ 直接进入较大 $dis$ 的节点的右子树，直到为空，然后并上去即可。

注意回溯时要注意维护左偏树。

4. 例题

T1：左偏树（可并堆）

题目传送门 Luogu

题目传送门 AcWing

可以使用并查集来维护数之间的合并关系。

AcWing 不需讨论已被删除的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e5+10,INF=0x3f3f3f3f;

struct Node{
    int l,r,v,p,dis;
    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define v(x) tr[x].v
    #define p(x) tr[x].p
    #define d(x) tr[x].dis
}tr[N];
int idx;

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

int merge(int a,int b)
{
    if (!a) return b;
    if (!b) return a;
    if (cmp(b,a)) swap(a,b);
    r(a)=merge(r(a),b);
    if (d(r(a))>d(l(a))) swap(r(a),l(a));
    d(a)=d(r(a))+1;
    return a;
}

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

int main()
{
    int n;
    scanf("%d",&n);
    v(0)=INF;
    while (n--)
    {
        int t,x,y;
        scanf("%d %d",&t,&x);
        if (t==1)
        {
            v(++idx)=x;
            d(idx)=1;
            p(idx)=idx;
        }
        else if (t==2)
        {
            scanf("%d",&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 (t==3)
        {
            printf("%d\n",v(find(x)));
        }
        else if (t==4)
        {
            x=find(x);
            if (cmp(r(x),l(x))) swap(l(x),r(x));
            p(x)=l(x),p(l(x))=l(x);
            merge(l(x),r(x));
        }
    }
    return 0;
}

而 Luogu 不同，处理起来略显麻烦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e5+10,INF=0x7fffffff;

struct Node{
    int l,r,v,p,dis;
    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define v(x) tr[x].v
    #define p(x) tr[x].p
    #define d(x) tr[x].dis
}tr[N];
int idx;

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

int merge(int a,int b)
{
    if (!a) return b;
    if (!b) return a;
    if (cmp(b,a)) swap(a,b);
    r(a)=merge(r(a),b);
    if (d(r(a))>d(l(a))) swap(r(a),l(a));
    d(a)=d(r(a))+1;
    return a;
}

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

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=0,x;i<n;++i)
    {
        scanf("%d",&x);
        v(++idx)=x;
        d(idx)=1;
        p(idx)=idx;
    }
    v(0)=INF;
    while (m--)
    {
        int t,x,y;
        scanf("%d %d",&t,&x);
        if (t==1)
        {
            scanf("%d",&y);
            if (x!=y&&v(x)!=INF&&v(y)!=INF)
            {
                x=find(x);y=find(y);
                if (cmp(y,x)) swap(x,y);
                p(y)=x;
                merge(x,y);
            }
        }
        else if (t==2)
        {
            if (v(x)==INF)
            {
                puts("-1");
                continue;
            }
            printf("%d\n",v(find(x)));
            x=find(x);
            v(x)=INF;
            if (cmp(r(x),l(x))) swap(l(x),r(x));
            p(x)=l(x),p(l(x))=l(x);
            merge(l(x),r(x));
        }
    }
    return 0;
}

T2：数字序列

题目传送门 Luogu

题目传送门 AcWing

首先，把每个数都减一个 $i$，即 $a[i]\leftarrow a[i]-i,b[i]\leftarrow b[i]-i$。

所以 $b[1]\leq b[2]\leq…\leq b[n]$。

计算处理后的答案，答案不变。

我们假设所有的 $b[i]$ 都相等，那么问题转化为“货仓选址”问题。

假设可以划为两段，前后各自取自己 $b[i]$ 相同的最小值。

再设前面一段取最小值时 $b[i]=u$，后一段 $b[i]=v$。

第一种情况时 $u\leq v$，则直接保留，即是整段的最优解。

那第二种情况 $u>v$ 怎么办呢？

证明：答案 $ans$ 是 $a$ 中位数 ，表示新的 $b[i]$。

假设前一段是 $b[1…n]$，后一段是 $b[n + 1…m]$。

首先，证明，$b[n]\leq u,b[n+1]\geq v$。

证明一个：假设 $b[n] > u$，我们可以将 $b[1…n]$ 全部替换为 $u$，很明显前面的答案不会变大，而且留给后面的空间是越大的，答案不会变差。

那么，我们接着证明 $b[1…n]$ 变成相同的 $b[1] > u$，是不会变差的。

首先，可以得到 $a[1…n]$ 的中位数 $s$ 一定是 $\leq u$。如果 $s > u$ 的话，我们可以将 $u$ 向上移动，变为 $s$。因为有 $\dfrac{n}{2}$ 个数大于 $s$，那么答案是一定会变小的。

我们可以将 $b[2…n]$ 都减去一个 $b[2] - b[1]$，那么此时 $b[1] = b[2]$。看到有 $\dfrac n2$ 个数小于 $u$，于是向下移动的话，会导致答案变小。我们对于每一个都这么操作，最后一定会得到 $b[1..n] = b[1]$。

然后，我们再证明 $b[1]$ 向下移动一定会使答案变小。这个显然。

现在，我们已经得到 $b[n]\leq u,b[n+1]\geq v$，且两段都是一样的。

接着就是根据中位数，我们可以将他们调整为 $a[1…n + m]$ 的中位数。肯定说的不清楚，只好先鸽着了。

最后直接维护每一段的大小和长度，如果遇到递减，则合并为中位数，就可以了。