P5494 题解 & 平衡树合并

这是一篇平衡树合并题解，平衡树合并的复杂度 并不是假的，本题复杂度 $O(n \log n)$，更通用的可以证明到 $O(\log^2 n)$，比如支持序列 全局加全局取膜。

https://codeforces.com/blog/entry/108601

和上面的分析相同，但受个人水平所限可能有误，还希望多多包涵，注意下文 $n,V$ 不分。

平衡树比线段树适用性更广，常数也不大（未卡常 fhqtreap 用时 615ms）。

平衡树合并

先不考虑分裂，单说合并。

现在要合并 $x,y$ 两棵树，选根节点堆值大的当根（假设是 $x$），把 $y$ 的子树按照 $x$ 的键值裂开（这里的裂开就是 treap 的 split），裂开的两瓣和 $x$ 的左右儿子递归下去合并。

1
2
3
4
5
6
7
8
9
10
11
12

int Merge(int x,int y){
    if(!x||!y)
        return x|y;
    if(tr[x].pri<tr[y].pri)
        swap(x,y);
    int l,r;
    split(y,tr[x].v,l,r);
    tr[x].l = Merge(tr[x].l,l);
    tr[x].r = Merge(tr[x].r,r);
    pushup(x);
    return x;
}

明显是把小的树裂开更优，但是堆值大大概率就是树大的，下文也默认此情况（主要是带有随机的不会分析）。

其实这里存在一个合不合并相同结点的问题，其实是 要合并 的，因为 treap 的复杂度依赖于树和堆的唯一性，如果存在相同结点那么可能会失去性质（比如全部都一样，可以在不违反树和堆的情况下出来一条链），对于一般的 treap 不存在此问题，因为自带了一个插入时间的比较。

现在分析平衡树合并的复杂度，设第一棵树大小为 $a$，第二棵为 $b$，不难发现单次合并的复杂度 上界 为 $O(\min(a,b)\log(\frac{\max(a,b)}{\min(a,b)}))$，大概是把小的树每个节点都拿去切割大的树，由于 finger search 所以切割复杂度为 $\log(\frac{\max(a,b)}{\min(a,b)})$。总复杂度为 $O(n \log n)$。

为什么说是上界，因为在两颗树值域重合少的时候复杂度和最少不相交的值域段数 $k$ 有关，合并一次的复杂度为 $O(k \log n)$。

本题的复杂度分析

由于合并 $k$ 段值域不相交的复杂度为 $O(k \log n)$，而一次 split 只会产生一段。问题是 $[l,x][x+1,y][y+1,r]$ 如果先合并 $[l,x][y+1,r]$ 再合并 $[x+1,y]$ 会产生额外的一次 $O(\log n)$，但是合并次数等于分裂次数，所以总复杂度为 $O(n \log n)$。

更通用的复杂度分析

定义势能为 $\varphi(T)=\sum\log(v_{i+1}-v_i)$，也就是 $T$ 相邻的两个值的差的 $\log$ 之和。

合并 $A$ 和 $B$，有 $k$ 段值域：

$$\begin{aligned} &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{<-d_1->}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{<--d_2-->}\ \ \ \ \ \ \ \ \ \ _{<--d_3-->}\ \ \ \ \ \ \ \ \ \ _{<---d_4--->}\\ &A = \{_{[--a_1--]}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{[-a_2-]}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{[--a_3--]}&\}\\ &B = \{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{[---b_1---]}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{[-b_2-]}&\} \end{aligned}$$

形如 $_{[-----]}$ 的是一段值域，形如 $_{<--d_i-->}$ 的是值域之间的距离且距离为 $d_i$。

合并后 $\Delta\varphi=\varphi(A)+\varphi(B)-\varphi(A\cup B)$，有

$$\Delta\varphi=\log(d_1+b_1+d_2)+\log(d_2+a_2+d_3)+\dots+\log(d_{k-1}+a_{\frac{k}{2}}+d_k)-(\log d_1+\dots+\log d_k)$$

前面的把 $\log(+a_i+)$ 的放在一起就是根据定义算的 $\varphi(A)$，后面的则是由于两段值域不交合并会产生新的势能，势能大小为 $\log$ 值域的距离也就是 $\log(d_i)$。

显然有

$$\Delta\varphi\geq\log(d_1+d_2)+\log(d_2+d_3)+\dots+\log(d_{k-1}+d_k)-(\log d_1+\dots+\log d_k)$$

因为 $\log$ 函数是下凸的，可得 $\log(\frac{a+b}{2})\geq \frac{\log a+\log b}{2}$，把 $\log$ 里的 $\frac{1}{2}$ 拿出来可得

$$\log(a+b)\geq 1+\frac{\log a+\log b}{2}$$

那么把 $\log(d_{i-1}+d_i)$ 全部拆开，可得

$$\Delta\varphi\geq k-1-\frac{d_1+d_k}{2}$$

忽略常数可得

$$\Delta\varphi\geq k-O(\log V)$$

也就是说最多做 $n \log V$ 次 split，总复杂度为 $O(n \log V \log n)$。

带有分裂的复杂度分析

一次分裂会减少 $\log V$ 的势能，split 是不增加势能的。

一次合并如果增加就至多增加 $\log V$ 的势能（原因可以看上面的式子）。

那么最多就只有 $n\log V$ 的势能，而 $\Delta \varphi$ 最大就是把这些势能都减少完，所以总复杂度为 $O(n \log n \log V)$。

代码

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

const int N = 200005;
int n,m;

mt19937 myrand(713);
class fhqtreap{
    private:
        struct{int l,r,v,s,siz;unsigned pri;} tr[2*N];
        int rt[N];
        int idx;
        
        int create(int v,int s){tr[++idx] = {0,0,v,s,s,myrand()};return idx;}
        void pushup(int u){tr[u].siz = tr[tr[u].l].siz+tr[tr[u].r].siz+tr[u].s;}
    public:
        int& operator [] (const int &x){return rt[x];}
        void split(int u,int c,int &x,int &y){
            if(!u){
                x = y = 0;
                return;
            }
            if(tr[u].v<=c){
                x = u;
                split(tr[u].r,c,tr[x].r,y);
            }
            else{
                y = u;
                split(tr[u].l,c,x,tr[y].l);
            }
            pushup(u);
        }
        void split_rk(int u,int c,int &x,int &y){
            if(!u){
                x = y = 0;
                return;
            }
            if(tr[tr[u].l].siz+tr[u].s<=c){
                x = u;
                split_rk(tr[u].r,c-tr[tr[u].l].siz-tr[u].s,tr[x].r,y);
            }
            else{
                y = u;
                split_rk(tr[u].l,c,x,tr[y].l);
            }
            pushup(u);
        }
        int merge(int x,int y){
            if(!x||!y)
                return x|y;
            if(tr[x].pri>tr[y].pri){
                tr[x].r = merge(tr[x].r,y);
                pushup(x);
                return x;
            }
            tr[y].l = merge(x,tr[y].l);
            pushup(y);
            return y;
        }
        int Merge(int x,int y){
            if(!x||!y)
                return x|y;
            if(tr[x].pri<tr[y].pri)
                swap(x,y);
            int l,r;
            split(y,tr[x].v,l,r);
            tr[x].l = Merge(tr[x].l,l);
            tr[x].r = Merge(tr[x].r,r);
            pushup(x);
            return x;
        }
        void insert(int &u,int c,int s){
            int x,y;
            split(u,c,x,y);
            u = merge(merge(x,create(c,s)),y);
        }
        int kth(int &u,int K){
            int x,y;
            split_rk(u,K-1,x,y);
            int p = y;
            while(tr[p].l)
                p = tr[p].l;
            u = merge(x,y);
            return p?tr[p].v:-1;
        }
        int count(int &u,int l,int r){
            int x,y,z;
            split(u,l-1,x,y);
            split(y,r,y,z);
            int ans = tr[y].siz;
            u = merge(merge(x,y),z);
            return ans;
        }
        void move(int &x,int &y,int l,int r){
            int a,b,c;
            split(x,l-1,a,b);
            split(b,r,b,c);
            y = b;
            x = merge(a,c);
        }
}tr;

signed main(){
    n = in,m = in;
    for(int k=1;k<=n;k++)
        tr.insert(tr[1],k,in);
    int idx = 1;
    while(m--){
        int op = in,p = in;
        if(!op){
            int x = in,y = in;
            tr.move(tr[p],tr[++idx],x,y);
        }
        else if(op==1){
            int t = in;
            tr[p] = tr.Merge(tr[p],tr[t]);
        }
        else if(op==2){
            int x = in,q = in;
            tr.insert(tr[p],q,x);
        }
        else if(op==3){
            int x = in,y = in;
            out(tr.count(tr[p],x,y),'\n');
        }
        else
            out(tr.kth(tr[p],in),'\n');
    }
    return 0;
}

全局加全局取膜

全局加不影响势能。

如果取模的过程中把树分成了 $k$ 段，合并后产生了至多 $(k-1) \log v$ 的势能，但是 $v$ 也会变成 $\dfrac{v}{k}$。把 $\log v$ 提到外面来，显然每轮最劣的 $k$ 都是一样的，因为这是一个递归的问题。原问题变成了 $k$ 使得 $k\log_k n$ 最大。解得最小值取 $e$，最大值为 $n$。所以增加的势能最大为 $n \log v$。

所以总复杂度为 $O(n \log n\log v)$。

通用性

确实这东西很能拓展，只要不咋影响势能都可以把合并当作基本操作，比如加、除、取膜、开根、翻转。

其实全局取膜作用与值域区间也是对的，值域区间完全可以把它当成两个独立的序列分别操作后再 merge 起来，分别操作也就是 $(n-m)\log v+m \log v= n\log v$，完全不影响。最后只是常数段的 merge 新增的 $\log v$ 的势能。所以只会增加总共 $n \log v$ 的势能。别的同理。