首页 > 其他分享 >重链剖分题目选讲

重链剖分题目选讲

时间：2024-05-01 11:33:05浏览次数：31  
标签：剖分 int res top 选讲 dep lca 重链 root

染色

给定一棵 \(n\) 个节点的无根树，共有 \(m\) 个操作，操作分为两种：

  1. 将节点 \(a\) 到节点 \(b\) 的路径上的所有点（包括 \(a\) 和 \(b\)）都染成颜色 \(c\)。
  2. 询问节点 \(a\) 到节点 \(b\) 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。

这道题是树剖好题。我们来寻思如何改进树剖完成题目操作。下面是一个普通树剖，求路径和。

int query_uv(int u, int v) {
    int res = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, id[top[u]], id[u]);
        u = f[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    res += query(1, id[v], id[u]);
    return res;
}

我们肯定要将第 5 行线段树的 query 改成求连续段数量的函数。这个用线段树维护其实并不困难。见如下代码：

struct node {
	int lc, rc, sum;
};
struct segment {
	#define ls p << 1
	#define rs p << 1 | 1
	struct edge {
		int l, r, lc, rc, sum, lazy; // lc左端点颜色，rc右端点颜色，sum颜色端数量
	}tree[N * 4];
	
	void down(int p, int x) {
		tree[p].lc = tree[p].rc = tree[p].lazy = x;
		tree[p].sum = 1;
	}
	void push_up(int p) {
		tree[p].lc = tree[ls].lc;
		tree[p].rc = tree[rs].rc;
		tree[p].sum = tree[ls].sum + tree[rs].sum;
		if (tree[ls].rc == tree[rs].lc) tree[p].sum--;
	}
	void push_down(int p) {
		if (tree[p].lazy) {
			down(ls, tree[p].lazy);
			down(rs, tree[p].lazy);
			tree[p].lazy = 0;
		}
	}
	
	void build(int p, int l, int r) {
		tree[p].l = l, tree[p].r = r;
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
	}
	void modify(int p, int l, int r, int x) { // 区间赋值
		if (l <= tree[p].l && tree[p].r <= r) {
			down(p, x);
			return;
		}
		push_down(p);
		int mid = (tree[p].l + tree[p].r) >> 1;
		if (l <= mid) modify(ls, l, r, x);
		if (r > mid) modify(rs, l, r, x);
		push_up(p);
	}
	
	
	node query(int p, int l, int r) { // node 返回{左端点颜色，右端点颜色，颜色端数量}这个整体信息
		if (l > tree[p].r || r < tree[p].l) return {-1, 0, 0};
		if (l <= tree[p].l && tree[p].r <= r) return {tree[p].lc, tree[p].rc, tree[p].sum};
		push_down(p);
		node x = query(ls, l, r), y = query(rs, l, r), res;
		if (x.lc == -1) return y;
		if (y.lc == -1) return x;
		res.lc = x.lc, res.rc = y.rc;
		res.sum = x.sum + y.sum - (x.rc == y.lc);
		return res;
	}
}tr;

考虑树剖的过程，如果这次跳的路径的底端和底端下面那个点颜色相同，则需要将颜色端数量减一。

int query_path(int u, int v) {
	int res = 0, t1 = -1, t2 = -1; // 维护t1,t2,代表当前u,v下方的颜色
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(t1, t2);
		node tmp = tr.query(1, id[top[u]], id[u]);
		// tmp.lc是top[u]的颜色
		// tmp.rc是u的颜色
		res += tmp.sum;
		if (t1 == tmp.rc) res--;
		t1 = tmp.lc; // 更新
		u = fat[top[u]];
	}
	if (dep[u] < dep[v]) swap(u, v), swap(t1, t2);
	node tmp = tr.query(1, id[v], id[u]);
	res += tmp.sum;
	if (tmp.rc == t1) res--;
	if (tmp.lc == t2) res--;
	return res;
}

CF916E Jamie and Tree

有一棵 \(n\) 个节点的有根树，标号为 \(1\sim n\)，你需要维护以下三种操作

  1. 1 v：给定一个点 \(v\)，将整颗树的根变为 \(v\)。

  2. 2 u v x：给定两个点 \(u,v\) 和整数 \(x\)，将 \(\operatorname{lca}(u, v)\) 为根的子树的所有点的点权都加上 \(x\)。

  3. 3 v：给定一个点 \(v\)，你需要回答以 \(v\) 所在的子树的所有点的权值和。

这道题主要是加入了换根操作。设当前根节点为 \(root\)。

如果求 \(lca(u,v)\)，你只需要知道：\(lca(u,v)\) 等于 \(lca(u,root),lca(v,root),lca(u,v)\) 当中深度最大的那个点。具体证明略。

如果是对 \(u\) 子树操作，需要分情况：

  • 如果 \(u=root\)，就是对整棵树进行操作。

  • 如果 \(root\) 为 \(u\) 子树，见下图。

    image

    \(u\) 下方的靠近 \(root\) 的那个儿子叫做 \(t\)。可以这样操作：先把整棵树进行加，再把 t 子树减回去。灰色部分就是被操作的点。

  • 如果 \(u\) 为 \(root\) 子树，则直接对 \(u\) 进行操作即可。

#include <bits/stdc++.h>
using namespace std;
 
#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long
const int N = 3e5 + 5;
 
int n, m, a[N], sz[N], son[N], din[N], dep[N], idx, top[N], fat[N], id[N], cc, root;
vector<int> G[N];
 
struct fenwick {
	int c[N][2];
	void add(int x, int v) {
		for (int i = x; i <= N - 5; i += i & -i) {
			c[i][0] += v;
			c[i][1] += x * v;
		}
	}
	void modify(int l, int r, int v) {
		add(l, v);
		add(r + 1 , -v);
	}
	int sum(int op, int x) {
		int res = 0;
		for (int i = x; i; i -= i & -i) res += c[i][op];
		return res;
	}
	int query(int l, int r) {
		int t1 = sum(0, l - 1) * l - sum(1, l - 1);
		int t2 = sum(0, r) * (r + 1) - sum(1, r);
		return t2 - t1;
	}
}tr;
 
void dfs1(int u, int fa, int depth) {
	dep[u] = depth; sz[u] = 1; fat[u] = fa; din[u] = ++cc;
	for (auto v : G[u]) {
		if (v == fa) continue;
		dfs1(v, u, depth + 1);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}
 
void dfs2(int u, int fa, int tt) {
	top[u] = tt; id[u] = ++idx;
	if (!son[u]) return;
	dfs2(son[u], u, tt);
	for (auto v : G[u]) {
		if (v == fa || v == son[u]) continue;
		dfs2(v, u, v);
	}
}
 
int lca(int u, int v) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fat[top[u]];
	}
	if (dep[u] < dep[v]) return u;
	return v;
}
 
int get_son(int u, int v) { // 找v的儿子在u,v路径上
	while (top[u] != top[v]) {
		if (fat[top[u]] == v) return top[u];
		u = fat[top[u]];
	}
	return son[v];
} 
 
int get_lca(int x, int y, int root) {
	PII t[3];
	t[0] = {dep[lca(x, y)], lca(x, y)};
	t[1] = {dep[lca(x, root)], lca(x, root)};
	t[2] = {dep[lca(y, root)], lca(y, root)};
	sort(t, t + 3);
	return t[2].second;
}
 
 
signed main() {
	cin >> n >> m;
	_for(i, 1, n) cin >> a[i];
	_for(i, 1, n - 1) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0, 1);
	dfs2(1, 0, 1);
	_for(i, 1, n) tr.modify(din[i], din[i], a[i]);
	while (m--) {
		int op, u, v, x;
		cin >> op >> u;
		if (op == 1) root = u;
		else if (op == 2) {
			cin >> v >> x;
			int t = get_lca(u, v, root);
			if (t == root) tr.modify(1, n, x);
			else if (din[root] >= din[t] && din[root] <= din[t] + sz[t] - 1) {
				int tmp = get_son(root, t);
				tr.modify(1, n, x);
				tr.modify(din[tmp], din[tmp] + sz[tmp] - 1, -x);
			}
			else tr.modify(din[t], din[t] + sz[t] - 1, x);
		}
		else {
			int res = 0;
			if (u == root) res = tr.query(1, n);
			else if (din[root] >= din[u] && din[root] <= din[u] + sz[u] - 1) {
				int tmp = get_son(root, u);
				res += tr.query(1, n);
				res -= tr.query(din[tmp], din[tmp] + sz[tmp] - 1);
			}
			else res += tr.query(din[u], din[u] + sz[u] - 1);
			cout << res << endl;
		}
	}
}

标签：剖分,int,res,top,选讲,dep,lca,重链,root
From： https://www.cnblogs.com/stOtue/p/18169127

相关文章

  • 构造题选讲 by_chance
    不知道会不会有方法论，先咕了。upd：有的捏，但是好像没啥用/qdARC145DNonArithmeticProgressionSet首先考虑如何构造\(n\)个数满足不存在\(2y=x+z\)。考虑一个分治：将值域均匀分成三部分，并且让所有数平分在第一部分和第三部分，直至为\(1\)就可以在值域内选一个位置扔进去。......
  • 树链剖分
    link1link2前言：树链剖分实际上就是一种将树形结构剖分成一条条链状结构，并用线性数据结构来快速维护信息。重链剖分：一些定义：重儿子：一个节点的重儿子定义为它的子节点中子树节点最大的节点。轻儿子：一个节点除重儿子外的所有儿子重边：一个节点到它的重儿子的边即为重边......
  • 树链剖分
    参考链接：https://www.cnblogs.com/dx123/p/16320467.html（感谢董晓老师）树链剖分求LCA比倍增快一些https://www.luogu.com.cn/problem/P3379#include<bits/stdc++.h>constintN=5e5+5;usingnamespacestd;intn,m,root;inth[N],ne[2*N],e[2*N],idx;intdep[N]......
  • ATCF 杂题选讲 LHF
    CF1329DDreamoonLikesStrings将原序列中\(s_i=s_{i+1}\)的位置拿出来，记这些位置的集合为\(S\)。考虑我们选择\(S\)相邻两个数，并且删除中间这一段会产生什么影响。如果两边的数不同，那么这两个位置都会在\(S\)中消失，否则，会在\(S\)中新加入一个为这个数的位置。我们总......
  • 树链剖分lca笔记
    树链剖分求lca参考资料：https://www.cnblogs.com/cangT-Tlan/p/8846408.html[树链剖分lca]大佬讲的很清楚%%%orz这篇博客是我的学习笔记。树链剖分：树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结......
  • 「树链剖分」 学习笔记
    一，树链剖分的思想与概述正如其名，树链剖分用于将树剖分成若干条链的形式，以维护树上路径的信息，其中剖分出的链有多种形式，最常见的是重链，还有长链或更多其它的链。其中剖分出的链为重链时，就引出了下文的主角「重链剖分」。重链剖分能保证划分出的每条重链上的节点DFS序连续，因此......
  • 不等式选讲
    不等式选讲一、均值不等式1.1定义这是我们一般说的均值不等式：对非负实数\(a,b\)，有\[a+b\geqslant2\sqrt{ab}\]等号成立当且仅当\(a=b\)。事实上，这个不等式来自于\[(x-y)^2\geqslant0\]即\[x^2+y^2\geqslant2xy\]再令\[x^2=a\\[10pt]y^2=b\\[10pt]\]其中\(a,b......
  • 树链剖分 学习笔记
    随便写一点。1.原理定义重儿子为子树内子树大小最大的任一个点，重边为重儿子向其父亲连的边，其余为轻边。根据定义，轻边的父亲的子树大小一定不小于这个点的子树大小的二倍。又可以证出重边数量是\(O(\logn)\)的。因此可以用线段树维护这个东西。2.应用2.1dsu2.2lca考......
  • 杂题选讲
    杂题选记写一点比较神奇的杂题。觉得出的都很有心意啊。抽屉原理抽屉原理通常不会在程序中出现，但是这是一个评价复杂度，人肉计算阈值的有时不错的方法。如果你要学习一些十分厉害的抽屉原理，可以翻高中奥林匹克小丛书·组合数学的第二章，上面写着一些比较复杂的抽屉。\(Rams......
  • 【学习笔记】树链剖分
    一、重链剖分1.定义&作用树链剖分用于解决在树上执行的操作，将树上操作变为区间操作。用区间来维护。2.主要思想&实现有一棵树然后，我们把边区分一下，有一些边是“重边”，其余的是“轻边”，像这样：（红边为重边，黑边为轻）重边和轻边如何确定呢？看每一个结点旁的红色数字，代表他......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99