线段树合并

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

主要思想：

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

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

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

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

题解：

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

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

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

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

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

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

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

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

  直接令新节点等于 \(++cnt\)。

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

完整代码：

#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;
}

完结撒花~