线段树合并
By WyyOIer |
2023-02-19 19:04:58 /
2023-02-25 09:01:34
阅读数 nan

算法流程

线段树合并是动态开点线段树使用的进阶技巧，实现的操作即为合并两棵线段树上的对应节点的信息，注意此信息应该具有可合并的性质。

具体的做法为：从两棵线段树的根节点开始向左右儿子递归，记录 merge(p1, p2) 表示两棵线段树分别走到了 $p_1$ 和 $p_2$ 节点，此时两棵树的节点对应着同一区间 $[L,R]$ 的合并。

分两种终止情况：

其余情况递归 merge(ls(p1), ls(p2)) 与 merge(rs(p1), rs(p2)) 即可。

代码

// 以维护加法合并为例
int merge(int p1, int p2, int l, int r) {
    if(p1 == 0 || p2 == 0) {
        return p1 + p2;
    }
    else if(l == r) {
        tree[p1].d += tree[p2].d;
        return p1;
    }
    int mid = (l + r) >> 1;
    tree[p1].l = merge(ls(p1), ls(p2), l, mid);
    tree[p1].r = merge(rs(p1), rs(p2), mid + 1, r);
    pushup(p1);
    return p1;
}

时间复杂度分析

对于一次递归，我们将两个线段树节点合并为一个线段树节点，因此每次递归总节点数改变量 $\mathcal{O}(1)$。不妨设合并前所有线段树节点数量为 $\mathcal{O}(n\log n)$，而合并后线段树节点数量仍为 $\mathcal{O}(n\log n)$，因此线段树节点改变数量为 $\mathcal{O}(n\log n)$，因此递归次数的时间复杂度仍为 $\mathcal{O}(n\log n)$。

但注意单次合并的复杂度并不是平均 $\mathcal{O}(\log n)$，而只有 $n$ 次合并的总时间复杂度为 $\mathcal{O}(n\log n)$ 的性质。

习题

P1456 Monkey King

考虑对每一只猴子与其朋友我们维护出一个集合，那么考虑一次决斗，就是在两只猴子所对应的集合中挑选最大强壮值的猴子，并将两个集合合并，这是左偏树模板题，现在我们尝试用线段树合并解决。

那么我们先用并查集维护猴子朋友的集合，在用值域线段树维护强壮值，最后线段树上二分找到最大强壮值即可，合并时需要使用线段树合并。

时间复杂度 $\mathcal{O}(n\log n)$。

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

我们尝试对树上每个节点维护一个值域线段树来统计每种颜色的数量，需要先对路径进行差分使修改次数降至 $\mathcal{O}(m)$，从而使总结点数保证在 $\mathcal{O}(m\log n)$。

最后在树上做线段树合并，找线段树上最大值即可。

时间复杂度 $\mathcal{O}(m\log n)$。

P1552 [APIO2012] 派遣

首先我们钦定领导为 $u$，那么 $c_u$ 确定之后，每个忍者的贡献相同，我们所做的只是贪心的选择花费最小的忍者，那么在线段树上二分可以求出最多选出的忍者数。

最后我们按照 dfs 序钦定领导并线段树合并维护，时间复杂度 $\mathcal{O}(n\log n)$。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, M;
int b[100005], c[100005], l[100005];

int rt[100005], node;

struct SegMent {
    int l, r, cnt;
    ll sum;
}tree[3200005];

ll ans;

inline int ls(int p) {return tree[p].l;}
inline int rs(int p) {return tree[p].r;}

void pushup(int p) {
    tree[p].cnt = tree[ls(p)].cnt + tree[rs(p)].cnt;
    tree[p].sum = tree[ls(p)].sum + tree[rs(p)].sum;
} 

int ins(int p, int l, int r, int x) {
    if(p == 0) {
        p = ++node;
    }
    if(l == r) {
        tree[p].cnt++;
        tree[p].sum += l;
    }
    else {
        int mid = (l + r) >> 1;
        if(x <= mid) {
            tree[p].l = ins(ls(p), l, mid, x);
        }
        else {
            tree[p].r = ins(rs(p), mid + 1, r, x);
        }
        pushup(p);
    }
    return p;
}

int merge(int p1, int p2, int l, int r) {
    if(p1 == 0 || p2 == 0) {
        return p1 + p2;
    }
    if(l == r) {
        tree[p1].cnt += tree[p2].cnt;
        tree[p1].sum += tree[p2].sum;
    }
    else {
        int mid = (l + r) >> 1;
        tree[p1].l = merge(ls(p1), ls(p2), l, mid);
        tree[p1].r = merge(rs(p1), rs(p2), mid + 1, r);
        pushup(p1);
    }
    return p1;
}

int que(int p, int l, int r, int k) {
    if(tree[p].sum <= k) {
        return tree[p].cnt;
    }  
    if(l == r) {
        return k / l;
    }
    int mid = (l + r) >> 1;
    if(tree[ls(p)].sum > k) {
        return que(ls(p), l, mid, k);
    }
    else {
        return tree[ls(p)].cnt + que(rs(p), mid + 1, r, k - tree[ls(p)].sum);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n >> M;
    for(int i = 1;i <= n;i++) {
        cin >> b[i] >> c[i] >> l[i];
    } 
    for(int i = n;i >= 1;i--) {
        rt[i] = ins(rt[i], 1, 1e9, c[i]);
        int num = que(rt[i], 1, 1e9, M);
        ans = max(ans, 1ll * num * l[i]);
        rt[b[i]] = merge(rt[b[i]], rt[i], 1, 1e9);
    }
    cout << ans << '\n';
    
    cout.flush();
    return 0;
}

P3521 [POI2011]ROT-Tree Rotations

考虑对于一个节点 $u$ 的左右儿子，如果逆序对数量 $>$ 正序对显然交换，且不会对后续其它交换造成影响，因此我们只需统计节点 $u$ 产生的正序对 $sum_0$ 与逆序对 $sum_1$，那么对答案的贡献就为 $\min(sum_0,sum_1)$。

现在考虑计算 $sum_0$ 和 $sum_1$。不妨设左子树 $p_1$，右子树 $p_2$，当我们在线段树合并的时候走到 $[L,R]$ 区间时，可以很自然地维护出 $p_2$ 中值域 $[1,L-1]$ 的数的数量 $pre$ 和值域 $[R+1,n]$ 的数的数量 $suf$。

维护方式很简单，当我们从 $[L,R]\rightarrow [L,mid]$ 时，加入 $p_2$ 中 $[mid+1,R]$ 至 $suf$；从 $[L,R]\rightarrow [mid+1,R]$ 时，加入 $p_2$ 中 $[L,mid]$ 至 $pre$，这样我们维护的信息永远是当前线段树合并的区间 $[L,R]$ 之外的信息。

统计信息只在合并终止情况时计算：

最后重复执行合并流程，统计答案即可。

时间复杂度 $\mathcal{O}(n\log n)$。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, lson[400005], rson[400005], v[400005], cnt, RT;
ll ans;

int read(int u) {
    if(u == 0) {
        u = ++cnt;
    }
    cin >> v[u];
    if(v[u] == 0) {
        lson[u] = read(lson[u]), rson[u] = read(rson[u]);
    }
    return u;
}

int rt[400005], node;

struct SegMent {
    int l, r, cnt;
}tree[4000005];

inline int ls(int p) {return tree[p].l;}
inline int rs(int p) {return tree[p].r;}

void pushup(int p) {
    tree[p].cnt = tree[ls(p)].cnt + tree[rs(p)].cnt;
}

int ins(int p, int l, int r, int x) {
    if(p == 0) {
        p = ++node;
    }
    if(l == r) {
        tree[p].cnt++;
    }
    else {
        int mid = (l + r) >> 1;
        if(x <= mid) {
            tree[p].l = ins(ls(p), l, mid, x);
        }
        else {
            tree[p].r = ins(rs(p), mid + 1, r, x);
        } 
        pushup(p);
    }
    return p;
}

ll sum0, sum1;

int merge(int p1, int p2, int l, int r, int pre, int suf) {
    if(p2 == 0) {
        sum0 += 1ll * suf * tree[p1].cnt;
        sum1 += 1ll * pre * tree[p1].cnt;
        return p1;
    }
    if(p1 == 0) {
        return p2;
    }
    int mid = (l + r) >> 1;
    int tmp = tree[ls(p2)].cnt;
    tree[p1].l = merge(ls(p1), ls(p2), l, mid, pre, suf + tree[rs(p2)].cnt);
    tree[p1].r = merge(rs(p1), rs(p2), mid + 1, r, pre + tmp, suf);
    pushup(p1);
    return p1;
}

void dfs(int u) {
    if(v[u] != 0) {
        rt[u] = ins(rt[u], 1, 2e5, v[u]);
    }
    else {
        dfs(lson[u]), dfs(rson[u]);
        sum0 = sum1 = 0;
        rt[u] = rt[lson[u]];
        rt[u] = merge(rt[u], rt[rson[u]], 1, 2e5, 0, 0);
        ans += min(sum0, sum1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n;
    RT = read(RT);
    dfs(RT);
    cout << ans << '\n';
    
    cout.flush();
    return 0;
}