浅谈线段树合并(洛谷P4556)

线段树合并

洛谷 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;
}

完结撒花~

上一篇:83行代码通关攻略|据说看的人都过了


下一篇:扇贝 Service Mesh 发展历程