首页 学习笔记

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

# 主要思想：

顾名思义，线段是合并就是将多棵线段树合并到一起，要求线段树维护的数据可以支持合并，例如最大值，区间和等。

我们在进行合并时要把两棵线段树上相同的结构点合并到一起，换句话说，就是两棵线段树当前要合并的点所表示的区间是一样的。

例如，区间长度是 88，那么我们合并时要把 [1,8][1,8] 和 [1,8][1,8] 合并到一起 [5,8][5,8] 和 [5,8][5,8] 合并到一起。

好了，我们知道了主要思想后下面来看如何实现。

# 题解：

  • 对于洛谷P4556这道题来说，我们要对这 nn 个房屋每个点都建一棵权值线段树。

    何为权值线段树：就是以题目中救济粮 zz 为下角标建线段树，维护每种救济粮个数以及最多的是哪种.

    sum[z]sum[z] 记录种类为 zz 的救济粮有多少。

    maxz[rt]maxz[rt] 记录第 rtrt 个房屋中数量最多的救济粮种类是多少。

  • 对于每次发放救济粮，暴力更新 xx 到 yy 的链是不现实的，这时我们就要用到树上差分的思想。

    令 sum[x]++，sum[y]++sum[x]++ ， sum[y]++ 且 sum[lca(x,y)]−−，sum[fa[lca(x,y)]]−−sum[lca(x,y)]-- ，sum[fa[lca(x,y)]]--，这样对于一个点来说，它的被覆盖次数（救济粮个数）就是以它为根的子树权值和。

    思考一下为什么，可以手玩一下，随便挑几个点试试（emm应该挺好理解的吧，这里不再赘述了）

  • 下面再来谈谈动态开点线段树，我们不需要把整棵树都建出来，需要用哪个点就建哪个点。

    直接令新节点等于 ++cnt++cnt。

    这样一来对于节点 rtrt ，它的左子树就不再是 rt<<1rt<<1，右子树也不再是 rt<<1∣1rt<<1|1，所以我们要存 ls[rt]ls[rt] 和 rs[rt]rs[rt]

# 完整代码：

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
128
#include <iostream>
#include <cstdio>
#define log 20

using namespace std;

const int N = 1e5 + 10;
const int M = 80 * N;
const int maxR = 1e5;
struct node{
    int v, nxt;
}edge[N << 1];
int head[N], tot;
int n, m, cnt;
int f[N][21], dep[N];
int sum[M], maxz[M], ls[M], rs[M];
int ans[N], root[N];

inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return f * x;
}

inline void add(int x, int y){
    edge[++tot] = (node){y, head[x]};
    head[x] = tot;
}

//----------------------------------------查找lca部分
//dfs预处理
void dfs(int x, int fa){
    f[x][0] = fa;
    dep[x] = dep[fa] + 1;
    for(int i = 1; i < log; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa) continue;
        dfs(y, x);
    }
}

//lca模板
int lca(int a, int b){
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = log - 1; i >= 0; i--)
        if(dep[f[a][i]] >= dep[b])
            a = f[a][i];
    if(a == b) return a;
    for(int i = log - 1; i >= 0; i--)
        if(f[a][i] != f[b][i]){
            a = f[a][i];
            b = f[b][i];
        }
    return f[a][0];
}

void pushup(int rt){
    if(sum[ls[rt]] >= sum[rs[rt]])
        sum[rt] = sum[ls[rt]], maxz[rt] = maxz[ls[rt]];
    else sum[rt] = sum[rs[rt]], maxz[rt] = maxz[rs[rt]];
}

//----------------------------------------动态开点 或 更新权值线段树
void update(int &rt, int l, int r, int z, int val){
    if(!rt) rt = ++cnt;        //动态开点
    if(l == r){
        sum[rt] += val;
        maxz[rt] = z;
        return;
    }
    int mid = (l + r) >> 1;
    if(z <= mid) update(ls[rt], l, mid, z, val);
    else update(rs[rt], mid + 1, r, z, val);
    pushup(rt);
}

//----------------------------------------线段树合并
int merge(int u, int v, int l, int r){
    if(!u || !v) return u + v;    //这里相当于一棵树为空的话，返回另一棵树，取个巧
    if(l == r){
        sum[u] += sum[v];
        return u;
    }
    int mid = (l + r) >> 1;
    ls[u] = merge(ls[u], ls[v], l, mid);
    rs[u] = merge(rs[u], rs[v], mid + 1, r);
    pushup(u);
    return u;
}

//----------------------------------------计算答案
void calc(int x, int fa){
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa) continue;
        calc(y, x);
        root[x] = merge(root[x], root[y], 1, maxR);        //整棵树从下到上合并
    }
    ans[x] = maxz[root[x]];
    if(!sum[root[x]]) ans[x] = 0;
}

int main(){
    n = read(), m = read();
    for(int i = 1; i < n; i++){
        int u, v;
        u = read(), v = read();
        add(u, v), add(v, u);
    }
    dfs(1, 0);
    while(m--){
        int x, y, z;
        x = read(), y = read(), z = read();
        int k = lca(x, y);
        update(root[x], 1, maxR, z, 1);            //树上差分
        update(root[y], 1, maxR, z, 1);
        update(root[k], 1, maxR, z, -1);
        update(root[f[k][0]], 1, maxR, z, -1);
    }
    calc(1, 0);
    for(int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
    return 0;
}

# End