比赛日志 / 算法

维护树上编号连续节点构成连通块/虚树的一种方法

维护连通块

现有一棵 nn 个节点的树。我们构建一最小的连通块 S(l,r)S(l,r)，包含编号在 [l,r][l,r] 中的所有节点。多次询问，每次对于任意一对 [l,r][l,r]，询问关于这连通块的信息。

如果可以离线/可持久化，此类问题有一通用思路：用扫描线维护“rr 固定时不同 ll 构成连通块的信息”。若 [p,q]⊆[l,r][p,q]\subseteq[l,r]，则 S(l,r)⊇S(p,q)S(l,r)\supseteq S(p,q)；对于一固定的 rr，我们维护 ll 分别取 r,r−1,⋯ ,1r,r-1,\cdots,1（向左拓展）时，连通块的增量。对于点 xx，我们记录 tr(x)t_r(x) 表示 rr 固定时使得 x∈S(l,r)x\in S(l,r) 的最大的 ll。假设已经对于 rr 维护好了；现在拓展到 r’=r+1r’=r+1。

若 x∉{r,r+1}x\notin \{r,r+1\}，则 tr+1(x)≠tr(x)t_{r+1}(x)\neq t_{r}(x) 是

  • xx 在 rr 到 r+1r+1 的简单路径上，且
  • tr+1(x)=rt_{r+1}(x)=r

的充分必要条件。

考虑任意 ll。由于 SS 是极小的，故将 r+1r+1“加入”S(l,r)S(l,r) 得到 S(l,r+1)S(l,r+1)，只需找到 r+1r+1 和连通块在树上最接近节点之间的路径，将路径上所有点加入连通块；由树的性质，此路径是通向 [l,r][l,r] 中任意节点的必经之路，也即 r,r+1r,r+1 的最短路径的某一前缀。又当 l=rl=r 时，S(l,r+1)S(l,r+1) 就是该路径本身；再有 [p,q]⊆[l,r]⟹S(l,r)⊇S(p,q)[p,q]\subseteq[l,r]\Longrightarrow S(l,r)\supseteq S(p,q)，故本命题得证。

因此，我们需将整条路径上的点的最大出现时间整体覆盖成 tr+1(x)=rt_{r+1}(x)=r（r+1r+1 本身除外，它是 tr+1(r+1)=r+1t_{r+1}(r+1)=r+1）。可以使用珂朵莉树和树剖维护连续的 t(x)t(x) 相同的一段。设 ΦΦ 表示连续段个数。每次覆盖操作会对 O⁡(log⁡n)\newcommand\bigO{\operatorname{O}}\bigO(\log n) 条重链执行“删除若干连续段，加入 O⁡(1)\bigO(1) 个连续段”的操作。又 Φ≤nΦ\leq n，则 ΦΦ 的总变化量是 O⁡(nlog⁡n)\bigO(n\log n) 的。因此若用对数级别有序关联式容器（如 std::map），总时间复杂度为 O⁡(nlog⁡2n)\bigO(n\log^2 n)。

例题 – MOCK PTS- 20231122 C – 树

给定大小为 nn 的树。qq 次询问。给定 [L,R][L,R]，计算 ∑l=LR∑r=lR∣S(l,r)∣−1. \sum_{l=L}^R\sum_{r=l}^R |S(l,r)|-1.

实际上是维护边的最大出现时间。如果我们对同一 rr 维护所有 ll 的 ∣S(l,r)∣−1|S(l,r)|-1，并称其为序列的一个版本，则求的就是版本号 r∈[L,R]r\in[L,R] 时序列 [L,R][L,R] 内元素的历史版本和。

考虑区间覆盖 t(x)t(x) 的过程。对于一个将要被删除的连续段，设其原最大出现时间为 t0t_0，其长度为 cc。我们将它从 t0t_0 提升到 rr，意味着“在 r+1r+1 及以后的版本中，(t0,r](t_0,r] 中的所有 ll 都有多 cc 条边在 S(l,… )S(l,\dots) 中”。对 (t0,r](t_0,r] 的所有点加上 cc 即可。使用线段树或树状数组，维护区间加、区间求历史版本和。时间复杂度 O⁡(nlog⁡2n+qlog⁡n)\bigO(n\log^2 n+q\log n)。

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
  81. 81
  82. 82
  83. 83
  84. 84
  85. 85
  86. 86
  87. 87
  88. 88
  89. 89
  90. 90
  91. 91
  92. 92
  93. 93
  94. 94
  95. 95
  96. 96
  97. 97
  98. 98
  99. 99
  100. 100
  101. 101
  102. 102
  103. 103
  104. 104
  105. 105
  106. 106
  107. 107
  108. 108
  109. 109
  110. 110
  111. 111
  112. 112
  113. 113
  114. 114
  115. 115
  116. 116
  117. 117
  118. 118
  119. 119
#include <bits/stdc++.h>
using namespace std;

#define inl inline
#define scd second
#define fst first
#define empb emplace_back
#define all(p) begin (p), end (p)
using ll = long long;
using ull = unsigned long long;
using pint = pair <int, int>;

constexpr int N = 1e5 + 10, G = 1<<18;
int n, m, fa[N], siz[N], hson[N], top[N], dep[N], dfn[N], dtot;
ll ans[N];
vector <int> e[N];
vector <pint> qu[N];
map <int, int> g;

void dfs (int x, int fr) {
	dep[x] = dep[fr] + 1;
	siz[x] = 1, fa[x] = fr;
	for (const int y : e[x]) {
		if (y == fr) continue;
		dfs (y, x), siz[x] += siz[y];
		if (siz[y] > siz[hson[x]])
			hson[x] = y;
	}
}
void decomp (int x, int tp) {
	top[x] = tp;
	dfn[x] = ++dtot;
	if (hson[x]) decomp (hson[x], tp);
	for (const int y : e[x])
		if (y != hson[x] && y != fa[x])
			decomp (y, y);
}

struct BIT {
	ll c[N], d[N];
	inl void __add (int x, ll dt) {
		const ll wdt = dt * x;
		for (; x <= n; x += x & -x)
			c[x] += dt, d[x] += wdt;
	}
	inl void add (int l, int r, ll dt) {
		__add (l, dt);
		__add (r + 1, -dt);
	}
	inl ll __ask (int x) const {
		ll s = 0, ws = 0;
		for (int y = x; y > 0; y &= y - 1)
			s += c[y], ws += d[y];
		return s * (x + 1) - ws;
	}
	inl ll ask (int l, int r) const {
		return __ask (r) - __ask (l - 1);
	}
} bit, wbit;

int main () {
	/* MOCK NOIP 20231122 吴秋实 */
	// freopen ("tree.in", "r", stdin);
	// freopen ("tree.out", "w", stdout);

	scanf ("%d", &n);
	for (int i = 1, x, y; i < n; ++i)
		scanf ("%d%d", &x, &y),
		e[x].empb (y), e[y].empb (x);
	dfs (1, 0); decomp (1, 1);
	scanf ("%d", &m);
	for (int i = 0, l, r; i < m; ++i)
		scanf ("%d%d", &l, &r),
		qu[r].empb (l, i);

	g[1] = g[n + 1] = 0;
	for (int x = 2; x <= n; ++x) {
		int u = x, v = x - 1;
		auto idou = [&] (int l, int r, int fr) {
			// 从 t0 = fr - 1 移动到 x - 1。
			const int len = r - l + 1;
			bit.add (max (fr, 1), x - 1, len);
			wbit.add (max (fr, 1), x - 1, (ll) len * x); // 历史版本和拆分常数贡献。
		};
		auto activ = [&] (int l, int r) {
			// 珂朵莉树核心代码。
			auto pt = g.upper_bound (l), it = prev (pt), qt = g.upper_bound (r);
			while (it != qt) {
				const int p = it->fst, q = pt->fst - 1, c = it->scd;
				idou (max (p, l), min (q, r), c);
				g.erase (it); it = pt++;
				if (l > p) g[p] = c;
				if (r < q) g[r + 1] = c;
			}
			g[l] = x;
		};
		while (top[u] != top[v]) {
			const int p = top[u], q = top[v];
			if (dep[p] >= dep[q]) {
				activ (dfn[p], dfn[u]);
				u = fa[p];
			} else {
				activ (dfn[q], dfn[v]);
				v = fa[q];
			}
		}
		if (dep[u] > dep[v]) swap (u, v);
		if (u != v) activ (dfn[u] + 1, dfn[v]);
		const ll s = bit.__ask (x), ws = wbit.__ask (x);
		for (const auto &[l, id] : qu[x])
			ans[id] = (s - bit.__ask (l - 1)) * (x + 1)
				- (ws - wbit.__ask (l - 1));
	}

	for (int i = 0; i < m; ++i)
		printf ("%lld\n", ans[i]);

	return 0;
}

维护虚树

记 T(l,r)T(l,r) 表示 [l,r][l,r] 中所有节点构成的虚树。有 T(l,r)={z∣∃x,y∈[l,r],lca⁡(x,y)=z}T(l,r)=\{z\mid \exists x,y\in[l,r],\newcommand\lca{\operatorname{lca}}\lca(x,y)=z\}，自然有 T(l,r)⊆S(l,r)T(l,r)\subseteq S(l,r)，且 [p,q]⊆[l,r]⟹T(l,r)⊇T(p,q)[p,q]\subseteq[l,r]\Longrightarrow T(l,r)\supseteq T(p,q) 仍成立。我们记 pr(x)p_r(x) 表示最大的 ll 使得 x∈T(l,r)x\in T(l,r)。

我们试图通过类似方式维护 rr 确定时所有 T(l,r)T(l,r) 的点集。不同于维护连通块，这下并不是 r+1,rr+1,r 间简单路径上的所有节点都能得到更新，且不一定有 pr+1(x)=rp_{r+1}(x)=r。我们需要一些更强的性质，方便精确更新 p(x)p(x)。

记从 r+1r+1 到 rr 的有向简单路径上节点依序为 y1,y2,⋯ ,yky_1,y_2,\cdots,y_k。则 ∀i,1≤i<k,tr(yi)≤tr(yi+1)\forall i,1\leq i<k,t_{r}(y_i)\leq t_{r}(y_{i+1})。

仍然考虑 l=r,r−1,⋯ ,1l=r,r-1,\cdots,1 时，S(l,r)S(l,r) 的逐步扩张——每次变成原先的超集。这条性质就很显然了。

记 z=lca⁡(x,y)z=\lca(x,y)。记从 r+1r+1 到 zz 的有向简单路径上节点依序为 y1=r+1,y2,⋯ ,yk=zy_1=r+1,y_2,\cdots,y_k=z。则 pr+1(yi)≠pr(yi)p_{r+1}(y_i)\neq p_r(y_i) 的充分必要条件是

  • yi=r+1∨(yi=z∧z≠r)y_i=r+1\lor(y_i=z\land z\neq r)，或
  • k>i>1∧tr(yi−1)≠tr(yi)k>i>1\land t_r(y_{i-1})\neq t_r(y_i)，即相同 tr(y)t_r(y) 连续段的最低节点。

pr+1(r+1)=r+1,pr+1(z)=rp_{r+1}(r+1)=r+1,p_{r+1}(z)=r。在 zz 到 rr 路径子树上的所有节点，其与 r+1r+1 的 lca⁡\lca 必然为 zz；在 zz 所有祖先的子树内的所有节点，其在 TT 中的存在不受到 r+1r+1 的影响。现在只需考虑所有 yiy_i 受 r+1r+1 加入的影响。

若 pr+1(yi)>pr(yi)p_{r+1}(y_i)>p_r(y_i)，则只可能是 yi=lca⁡(r+1,x),x=pr+1(yi)y_i=\lca(r+1,x),x=p_{r+1}(y_i)，且 xx 在 yiy_i 的与 r+1r+1 不同的子树中，且此时 xx 和 r+1r+1 是 yiy_i 子树中唯二的两个在 [x,r+1][x,r+1] 中的节点。仍考虑 S(l,r)S(l,r) 和 T(l,r)T(l,r) 以 ll 递减的顺序逐步扩张。tr(yi)≠tr(yi−1)t_r(y_i)\neq t_r(y_{i-1})，正说明存在这样一个 x,x=tr(yi)x,x=t_r(y_i)；且由 tr(yi)t_r(y_i) 的单调性，xx 应是 T(x,r)T(x,r) 和 S(x,r)S(x,r) 在 yiy_i 子树内的唯一一个节点。故而，r+1r+1 的加入使得 yi∈T(x,r+1)\T(x,r)y_i\in T(x,r+1)\backslash T(x,r)。

仿照上文维护 t(y)t(y) 的方式，我们只需在删除相同 t(y)t(y) 连续段时，维护其底端节点 yy 的 p(y)p(y)，将其赋为 tr(y)t_r(y) 即可。时间复杂度不变。

例题 – MOCK PTS- 20231124 B – 传奇特级法术树

给定以 11 为根的大小为 nn 的树。每条边有权值。qq 次询问，求 T(l,r)T(l,r) 所有节点有多少种不同的深度。

我们记 a(x)a(x) 表示 xx 的深度。“将 p(y)p(y) 从 p0p_0 提升到 tr(y)t_r(y)”意味着在 r+1r+1 及以后的版本，a(y)a(y) 将在 l≤tr(y)l\leq t_r(y) 的所有 T(l,r)T(l,r) 中出现。维护每种深度的最大出现时间，若从 ll 更新到 l’l’ 则将答案序列的 (l,l’](l,l’] 区间加一即可。时间复杂度 O⁡(nlog⁡2n+qlog⁡n)\bigO(n\log^2 n+q\log n)。

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
  81. 81
  82. 82
  83. 83
  84. 84
  85. 85
  86. 86
  87. 87
  88. 88
  89. 89
  90. 90
  91. 91
  92. 92
  93. 93
  94. 94
  95. 95
  96. 96
  97. 97
  98. 98
  99. 99
  100. 100
  101. 101
  102. 102
  103. 103
  104. 104
  105. 105
  106. 106
  107. 107
  108. 108
  109. 109
  110. 110
  111. 111
  112. 112
  113. 113
  114. 114
  115. 115
  116. 116
  117. 117
  118. 118
  119. 119
  120. 120
  121. 121
  122. 122
  123. 123
  124. 124
  125. 125
  126. 126
  127. 127
  128. 128
  129. 129
  130. 130
  131. 131
  132. 132
  133. 133
  134. 134
#include <bits/stdc++.h>
using namespace std;

#define inl inline
#define scd second
#define fst first
#define empb emplace_back
#define all(p) begin (p), end (p)
using ll = long long;
using ull = unsigned long long;
using pint = pair <int, int>;

constexpr int N = 1e5 + 10, M = 5e5 + 10;
int n, m, tc, ans[M], last[N], seq[N]; ll tt[N], d[N];
int siz[N], hson[N], top[N], fa[N], dep[N], dfn[N], dtot;
int head[N];
struct query { int l, nxt; } qu[M];
vector <pint> e[N];
map <int, int> g;

void dfs (int x, int fr) {
	siz[x] = 1; fa[x] = fr;
	dep[x] = dep[fr] + 1;
	for (const auto &[y, z] : e[x]) {
		if (y == fr) continue;
		d[y] = d[x] + z;
		dfs (y, x); siz[x] += siz[y];
		if (siz[y] >= siz[hson[x]])
			hson[x] = y;
	}
}
void decomp (int x, int tp) {
	top[x] = tp;
	dfn[x] = ++dtot;
	if (hson[x]) decomp (hson[x], tp);
	for (const auto &[y, z] : e[x])
		if (y != fa[x] && y != hson[x])
			decomp (y, y);
}

struct BIT {
	int c[N];
	inl void __add (int x, int dt) {
		for (; x <= n; x += x & -x) c[x] += dt;
	}
	inl void add (int l, int r) {
		__add (l, 1);
		__add (r + 1, -1);
	}
	inl int ask (int x) const {
		int res = 0;
		for (; x > 0; x -= x & -x) res += c[x];
		return res;
	}
} bit;
inl int rev (int x, int n = ::n) { return n - x + 1; }

int main () {
	/* MOCK PTS 20231124 吴秋实 */
	// freopen ("tree.in", "r", stdin);
	// freopen ("tree.out", "w", stdout);

	scanf ("%d%d", &n, &m);
	for (int i = 1, x, y, z; i < n; ++i) {
		scanf ("%d%d%d", &x, &y, &z);
		e[x].empb (y, z);
		e[y].empb (x, z);
	}

	dfs (1, 0);
	decomp (1, 1);
	memcpy (tt, d + 1, n<<3);
	sort (tt, tt + n);
	tc = unique (tt, tt + n) - tt;
	for (int x = 1; x <= n; ++x) {
		dfn[x] = rev (dfn[x]);
		seq[dfn[x]] = lower_bound (tt, tt + tc, d[x]) - tt;
	}

	for (int i = 1, l, r; i <= m; ++i) {
		scanf ("%d%d", &l, &r);
		if (l == r) ans[i] = 1;
		else qu[i] = { l, head[r] }, head[r] = i;
	}

	g[1] = g[n + 1] = 0;
	for (int x = 2; x <= n; ++x) {
		int u = x, v = x - 1, _c = 0;
		auto activ = [&] (int l, int r, auto escal) {
			auto qt = g.upper_bound (r),
				pt = g.upper_bound (l), it = prev (pt);
			while (it != qt) {
				const int c = it->scd, p = it->fst, q = pt->fst - 1;
				escal (max (l, p), c, _c);
				g.erase (it); it = pt++;
				if (p < l) g[p] = c;
				if (q > r) g[r + 1] = c;
			}
			g[l] = x;
		};
		auto escal = [&] (int idx, int c, int &_c) {
			if (_c == c) return;
			else _c = c;
			const int num = seq[idx], t = c - 1;
			if (last[num] < t) {
				bit.add (rev (t), rev (last[num] + 1));
				last[num] = t;
			}
		};
		while (top[u] != top[v]) {
			if (dep[top[u]] >= dep[top[v]]) {
				activ (dfn[u], dfn[top[u]], escal);
				u = fa[top[u]];
			} else {
				activ (dfn[v], dfn[top[v]], [] (int, int, int&) {});
				v = fa[top[v]];
			}
		}
		if (dfn[u] < dfn[v])
			activ (dfn[u], dfn[v] - 1, escal);
		else if (dfn[v] < dfn[u])
			activ (dfn[v], dfn[u] - 1, [] (int, int, int&) {});
		escal (max (dfn[u], dfn[v]), x, _c);
		escal (dfn[x], x + 1, _c);
		for (int id = head[x]; id; id = qu[id].nxt)
			ans[id] = bit.ask (rev (qu[id].l));
	}

	for (int i = 1; i <= m; ++i)
		printf ("%d\n", ans[i]);

	return 0;
}
  • 2023年11月30日

Tags:

You may also like...

成都外国语学校高二 OIer。喜欢搞些杂七杂八的小项目。常去骑车。复健中，脚力已不如前。

一言(ひとこと)

暫し空に祈りて 愛を断て

分类目录