算法笔记-线段树合并

线段树合并

前置知识：权值线段树、动态开点

将两棵线段树的信息合并成一棵线段树。
可以新建一颗线段树保存原来两颗线段树的信息，也可以将第二棵线段树维护的信息加到第一棵线段树上。

前者的空间复杂度较高，如果合并之前的线段树不会再用到的话，可以将第二颗线段树的信息加到第一棵线段树上。

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

题意：

一棵树有 $n$ 个点。每次操作 $(x,y,z)$ 在路径 $(x,y)$ 上的每一个点放一个救济粮 $z$。询问每个点存放最多的是哪种救济粮

解析：

对于树上一条路径上的点进行相同的操作，可以想到树上差分。

然后统计每个点最多的东西，可以用权值线段树维护每种救济粮的数目。

因为将发放救济粮转化成树上差分，求答案的时候需要合并，所以从下向上合并线段树。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int head[maxn], tot;
struct edge{int to, nxt;
}e[maxn << 1];
struct node{int mcnt, id;int ls, rs;
}t[maxn * 60];
struct query{int x, y, z;
}q[maxn];int cnt;
int n, m, MAX;
int rt[maxn], ans[maxn];
void add(int a, int b){e[++tot].nxt = head[a];e[tot].to = b;head[a] = tot;
}
int dep[maxn], siz[maxn], top[maxn], son[maxn], fa[maxn];
void dfs1(int u, int p){dep[u] = dep[p] + 1;siz[u] = 1;fa[u] = p;for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == p)continue;dfs1(v, u);siz[u] += siz[v];if(siz[v] > siz[son[u]])son[u] = v;}
}
void dfs2(int u, int tp){top[u] = tp;if(son[u])dfs2(son[u], tp);for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa[u] || v == son[u])continue;dfs2(v, v);}
}
int LCA(int u, int v){while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]])swap(u, v);u = fa[top[u]];}return dep[u] < dep[v] ? u : v;
}
void pushup(int k){if(t[t[k].ls].mcnt >= t[t[k].rs].mcnt){t[k].mcnt = t[t[k].ls].mcnt;t[k].id = t[t[k].ls].id;}else{t[k].mcnt = t[t[k].rs].mcnt;t[k].id = t[t[k].rs].id;}
}
void update(int &k, int l, int r, int pos, int v){if(k == 0)k = ++cnt;if(l == r && l == pos){t[k].mcnt += v;t[k].id = l;return;}int mid = (l+r) >> 1;if(pos <= mid)update(t[k].ls, l, mid, pos, v);elseupdate(t[k].rs, mid+1, r, pos, v);pushup(k);
}
void merge(int &a, int b, int l, int r){if(!a || !b){a = (!a ? b : a);return;}	if(l == r){t[a].mcnt += t[b].mcnt;t[a].id = l;return;}int mid = (l+r) >> 1;merge(t[a].ls, t[b].ls, l, mid);merge(t[a].rs, t[b].rs, mid+1, r);pushup(a);
}
void dfs(int u){for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa[u])continue;dfs(v);merge(rt[u], rt[v], 1, MAX);}if(t[rt[u]].mcnt != 0)ans[u] = t[rt[u]].id;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1, u, v; i < n; i++){cin >> u >> v;add(u, v);add(v, u);}dfs1(1, 0);dfs2(1, 1);for(int i = 1; i <= m; i++){cin >> q[i].x >> q[i].y >> q[i].z;MAX = max(MAX, q[i].z);}for(int i = 1; i <= m; i++){int u = q[i].x, v = q[i].y;int w = q[i].z;int lca = LCA(u, v);update(rt[u], 1, MAX, w, 1);update(rt[v], 1, MAX, w, 1);update(rt[lca], 1, MAX, w, -1);if(fa[lca])update(rt[fa[lca]], 1, MAX, w, -1);}dfs(1);for(int i = 1; i <= n; i++)cout << ans[i] << endl;return 0;
}

P1600 [NOIP2016 提高组] 天天爱跑步

题意：

一棵 $n$ 节点的树，有 $m$ 条路径，每个节点有参数 $w_i$。询问有多少条路径的第 $w_i+1$ 个点是节点 $i$。

解析：

对于每条路径 $(s,t)$，可以分成两条路径 $(s,lca)$ 和 $(lca,t)$，如果模拟这个过程的话，时间复杂度为 $O(nm)$ 不能接受。

换个角度考虑，对于每个点，有多少条路径会对该点产生贡献。

设节点 $i$ 的深度为 $de{p}_i$

设路径 $(s,t)$ 对节点 $u$ 产生贡献。

• $u$ 在 $(s,lca)$ 上。$de{p}_s-de{p}_u=w_u$
• $u$ 在 $(lca,t)$ 上。$de{p}_s+de{p}_u-2de{p}_{lca}=w_u$

即满足条件的路径会对节点 $u$ 有贡献。

考虑树上差分，在 $s$ 插入 $de{p}_s$，在 $t$ 处插入 $2de{p}_{lca}-de{p}_s$，在 $lca$ 处插入 $-de{p}_s$，在 $fa(lca)$ 处插入 $de{p}_s-2de{p}_{lca}$。后两者可以交换，然后线段树合并即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 3e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int head[maxn], cnt;
struct edge{int to, nxt;
}e[maxn << 1];
struct node{int v;int ls, rs;
}t[maxn * 60];
int n, m;
int rt[maxn], MAX, ans[maxn], w[maxn], tot;
void add(int a, int b){e[++cnt].nxt = head[a];e[cnt].to = b;head[a] = cnt;
} 
int siz[maxn], son[maxn], dep[maxn], fa[maxn], top[maxn];
void dfs1(int u, int p){dep[u] = dep[p]+1;siz[u] = 1;fa[u] = p;for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == p)continue;dfs1(v, u);siz[u] += siz[v]; if(siz[v] > siz[son[u]])son[u] = v;}
}
void dfs2(int u, int tp){top[u] = tp;if(son[u])dfs2(son[u], tp);for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == son[u] || v == fa[u])continue;dfs2(v, v);}
}
int LCA(int u, int v){while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]])swap(u, v);u = fa[top[u]];}return dep[u] < dep[v] ? u : v;
}
void update(int &k, int l, int r, int pos, int v){if(k == 0)k = ++tot;if(l == r && l == pos){t[k].v += v;return;}int mid = (l+r) >> 1;if(pos <= mid)update(t[k].ls, l, mid, pos, v);elseupdate(t[k].rs, mid+1, r, pos, v);return;
}
void merge(int &a, int b, int l, int r){if(!a || !b){a = (!a ? b : a);return;}if(l == r){t[a].v += t[b].v;return;}int mid = (l+r) >> 1;merge(t[a].ls, t[b].ls, l, mid);merge(t[a].rs, t[b].rs, mid+1, r);
}
int query(int k, int l, int r, int pos){if(!k)return 0;if(l == r)return t[k].v;int mid = (l+r) >> 1;if(pos <= mid)return query(t[k].ls, l, mid, pos);elsereturn query(t[k].rs, mid+1, r, pos);
}
void dfs(int u){for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa[u])continue;dfs(v);merge(rt[u], rt[v], 1, MAX);}if(w[u] && n + dep[u] + w[u] <= MAX)ans[u] += query(rt[u], 1, MAX, n + dep[u] + w[u]);ans[u] += query(rt[u], 1, MAX, n + dep[u] - w[u]);}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;MAX = n << 1;int u, v;for(int i = 1; i < n; i++){cin >> u >> v;add(u, v);add(v, u);}dfs1(1, 0);dfs2(1, 1);for(int i = 1; i <= n; i++)cin >> w[i];for(int i = 1; i <= m; i++){cin >> u >> v;int lca = LCA(u, v);update(rt[u], 1, MAX, n + dep[u], 1);update(rt[v], 1, MAX, n + dep[lca] * 2 - dep[u], 1);update(rt[lca], 1, MAX, n + dep[u], -1);update(rt[fa[lca]], 1, MAX, n + dep[lca] * 2 - dep[u], -1);}dfs(1);for(int i = 1; i <= n; i++)cout << ans[i] << " ";cout << endl;return 0;
}

P3224 [HNOI2012]永无乡

题意：

有 $n$ 个节点，每个节点有互不相同的重要程度。两种操作：

• 在 $(x,y)$ 之间建桥
• 询问与节点 $x$ 所在连通块中重要程度排名第 $k$ 小的节点编号

解析：

查询第 $k$ 小，考虑权值线段树；维护联通性，考虑并查集。在合并两个连通块时，也合并权值线段树

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 3e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;struct node{int sum, id;int ls, rs;
}t[maxn * 60];
int rt[maxn];
int tot, n, m, q;
int fa[maxn];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int pushup(int k){t[k].sum = t[t[k].ls].sum + t[t[k].rs].sum;
}
void update(int &k, int l, int r, int pos, int idx){if(k == 0)k = ++tot;if(l == r){t[k].sum++;t[k].id = idx;return;}int mid = (l+r) >> 1;if(pos <= mid)update(t[k].ls, l, mid, pos, idx);elseupdate(t[k].rs, mid+1, r, pos, idx);pushup(k);
}
void merge(int &a, int b, int l, int r){if(!a || !b){a = (a == 0 ? b : a);return;}if(l == r){t[a].sum += t[b].sum;return;}int mid = (l+r) >> 1;merge(t[a].ls, t[b].ls, l, mid);merge(t[a].rs, t[b].rs, mid+1, r);pushup(a);
}
int query(int a, int k, int l, int r){if(t[a].sum < k || !a)return 0;if(l == r)return t[a].id;int mid = (l+r) >> 1;int ans = 0;if(k <= t[t[a].ls].sum)ans = query(t[a].ls, k, l, mid);elseans = query(t[a].rs, k-t[t[a].ls].sum, mid+1, r);return ans;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1, p; i <= n; i++){fa[i] = i;cin >> p;update(rt[i], 1, n, p, i);}for(int i = 1, x, y; i <= m; i++){cin >> x >> y;int fx = find(x);int fy = find(y);fa[fy] = fx;merge(rt[fx], rt[fy], 1, n);}cin >> q;string op;for(int i = 1, x, y; i <= q; i++){cin >> op >> x >> y;if(op == "B"){int fx = find(x);int fy = find(y);if(fx == fy)continue;fa[fy] = fx;merge(rt[fx], rt[fy], 1, n); }else if(op == "Q"){int fx = find(x);int res = query(rt[fx], y, 1, n);if(res == 0)cout << -1 << endl;elsecout << res << endl;}}	return 0;
}