维护连通块
现有一棵 $n$ 个节点的树。我们构建一最小的连通块 $S(l,r)$，包含编号在 $[l,r]$ 中的所有节点。多次询问，每次对于任意一对 $[l,r]$，询问关于这连通块的信息。
如果可以离线/可持久化，此类问题有一通用思路：用扫描线维护“$r$ 固定时不同 $l$ 构成连通块的信息”。若 $[p,q]\subseteq[l,r]$，则 $S(l,r)\supseteq S(p,q)$；对于一固定的 $r$，我们维护 $l$ 分别取 $r,r-1,\cdots,1$（向左拓展）时，连通块的增量。对于点 $x$，我们记录 $t_r(x)$ 表示 $r$ 固定时使得 $x\in S(l,r)$ 的最大的 $l$。假设已经对于 $r$ 维护好了；现在拓展到 $r’=r+1$。
若 $x\notin \{r,r+1\}$，则 $t_{r+1}(x)\neq t_{r}(x)$ 是
- $x$ 在 $r$ 到 $r+1$ 的简单路径上，且
- $t_{r+1}(x)=r$
的充分必要条件。
考虑任意 $l$。由于 $S$ 是极小的，故将 $r+1$“加入”$S(l,r)$ 得到 $S(l,r+1)$，只需找到 $r+1$ 和连通块在树上最接近节点之间的路径，将路径上所有点加入连通块；由树的性质，此路径是通向 $[l,r]$ 中任意节点的必经之路，也即 $r,r+1$ 的最短路径的某一前缀。又当 $l=r$ 时，$S(l,r+1)$ 就是该路径本身；再有 $[p,q]\subseteq[l,r]\Longrightarrow S(l,r)\supseteq S(p,q)$，故本命题得证。
因此，我们需将整条路径上的点的最大出现时间整体覆盖成 $t_{r+1}(x)=r$（$r+1$ 本身除外，它是 $t_{r+1}(r+1)=r+1$）。可以使用珂朵莉树和树剖维护连续的 $t(x)$ 相同的一段。设 $Φ$ 表示连续段个数。每次覆盖操作会对 $\newcommand\bigO{\operatorname{O}}\bigO(\log n)$ 条重链执行“删除若干连续段，加入 $\bigO(1)$ 个连续段”的操作。又 $Φ\leq n$，则 $Φ$ 的总变化量是 $\bigO(n\log n)$ 的。因此若用对数级别有序关联式容器（如 std::map），总时间复杂度为 $\bigO(n\log^2 n)$。
例题
给定大小为 $n$ 的树。$q$ 次询问。给定 $[L,R]$，计算
$$
\sum_{l=L}^R\sum_{r=l}^R |S(l,r)|-1.
$$
实际上是维护边的最大出现时间。如果我们对同一 $r$ 维护所有 $l$ 的 $|S(l,r)|-1$，并称其为序列的一个版本，则求的就是版本号 $r\in[L,R]$ 时序列 $[L,R]$ 内元素的历史版本和。
考虑区间覆盖 $t(x)$ 的过程。对于一个将要被删除的连续段，设其原最大出现时间为 $t_0$，其长度为 $c$。我们将它从 $t_0$ 提升到 $r$，意味着“在 $r+1$ 及以后的版本中，$(t_0,r]$ 中的所有 $l$ 都有多 $c$ 条边在 $S(l,\dots)$ 中”。对 $(t_0,r]$ 的所有点加上 $c$ 即可。使用线段树或树状数组，维护区间加、区间求历史版本和。时间复杂度 $\bigO(n\log^2 n+q\log n)$。
#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 () {
/* */
// 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)$ 表示 $[l,r]$ 中所有节点构成的虚树。有 $T(l,r)=\{z\mid \exists x,y\in[l,r],\newcommand\lca{\operatorname{lca}}\lca(x,y)=z\}$，自然有 $T(l,r)\subseteq S(l,r)$，且 $[p,q]\subseteq[l,r]\Longrightarrow T(l,r)\supseteq T(p,q)$ 仍成立。我们记 $p_r(x)$ 表示最大的 $l$ 使得 $x\in T(l,r)$。
我们试图通过类似方式维护 $r$ 确定时所有 $T(l,r)$ 的点集。不同于维护连通块，这下并不是 $r+1,r$ 间简单路径上的所有节点都能得到更新，且不一定有 $p_{r+1}(x)=r$。我们需要一些更强的性质，方便精确更新 $p(x)$。
记从 $r+1$ 到 $r$ 的有向简单路径上节点依序为 $y_1,y_2,\cdots,y_k$。则 $\forall i,1\leq i<k,t_{r}(y_i)\leq t_{r}(y_{i+1})$。
仍然考虑 $l=r,r-1,\cdots,1$ 时，$S(l,r)$ 的逐步扩张——每次变成原先的超集。这条性质就很显然了。
记 $z=\lca(x,y)$。记从 $r+1$ 到 $z$ 的有向简单路径上节点依序为 $y_1=r+1,y_2,\cdots,y_k=z$。则 $p_{r+1}(y_i)\neq p_r(y_i)$ 的充分必要条件是
- $y_i=r+1\lor(y_i=z\land z\neq r)$，或
- $k>i>1\land t_r(y_{i-1})\neq t_r(y_i)$，即相同 $t_r(y)$ 连续段的最低节点。
$p_{r+1}(r+1)=r+1,p_{r+1}(z)=r$。在 $z$ 到 $r$ 路径子树上的所有节点，其与 $r+1$ 的 $\lca$ 必然为 $z$；在 $z$ 所有祖先的子树内的所有节点，其在 $T$ 中的存在不受到 $r+1$ 的影响。现在只需考虑所有 $y_i$ 受 $r+1$ 加入的影响。
若 $p_{r+1}(y_i)>p_r(y_i)$，则只可能是 $y_i=\lca(r+1,x),x=p_{r+1}(y_i)$，且 $x$ 在 $y_i$ 的与 $r+1$ 不同的子树中，且此时 $x$ 和 $r+1$ 是 $y_i$ 子树中唯二的两个在 $[x,r+1]$ 中的节点。仍考虑 $S(l,r)$ 和 $T(l,r)$ 以 $l$ 递减的顺序逐步扩张。$t_r(y_i)\neq t_r(y_{i-1})$，正说明存在这样一个 $x,x=t_r(y_i)$；且由 $t_r(y_i)$ 的单调性，$x$ 应是 $T(x,r)$ 和 $S(x,r)$ 在 $y_i$ 子树内的唯一一个节点。故而，$r+1$ 的加入使得 $y_i\in T(x,r+1)\backslash T(x,r)$。
仿照上文维护 $t(y)$ 的方式，我们只需在删除相同 $t(y)$ 连续段时，维护其底端节点 $y$ 的 $p(y)$，将其赋为 $t_r(y)$ 即可。时间复杂度不变。
例题
给定以 $1$ 为根的大小为 $n$ 的树。每条边有权值。$q$ 次询问，求 $T(l,r)$ 所有节点有多少种不同的深度。
我们记 $a(x)$ 表示 $x$ 的深度。“将 $p(y)$ 从 $p_0$ 提升到 $t_r(y)$”意味着在 $r+1$ 及以后的版本，$a(y)$ 将在 $l\leq t_r(y)$ 的所有 $T(l,r)$ 中出现。维护每种深度的最大出现时间，若从 $l$ 更新到 $l’$ 则将答案序列的 $(l,l’]$ 区间加一即可。时间复杂度 $\bigO(n\log^2 n+q\log n)$。
#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 () {
/* */
// 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;
}