题解：Old Orhei 路径查询系统

算法标签

• 线段树（Segment Tree）
• 状态转移函数复合
• 函数式线段树
• 区间查询与单点更新

问题分析

题目要求处理一个状态转移系统：

• 有 $N$ 个节点（考古遗址）
• 每条道路 $i$ 定义了一个部分函数：如果当前在起点 $X_i$，则转移到终点 $Y_i$，否则保持不变
• 数组 $A$ 中的每个元素对应应用一条道路的转移规则
• 需要支持：区间查询（应用一段连续的道路序列后的最终位置）和单点修改（改变某条道路）

核心思路

1. 函数复合的视角

将每条道路看作一个函数 $f_i: [1, N] \to [1, N]$：

$$f_i(u) = \begin{cases} Y_i & \text{if } u = X_i \\ u & \text{otherwise} \end{cases} $$

那么应用道路序列 $A_l, A_{l+1}, \dots, A_r$ 相当于计算函数复合：

$$F_{[l,r]} = f_{A_r} \circ f_{A_{r-1}} \circ \cdots \circ f_{A_l} $$

2. 线段树维护函数复合

代码的关键创新：用线段树的每个节点存储一个完整的转移函数。

对于线段树节点 $[l, r]$，存储函数 $nodes[id]$：

• $nodes[id][u]$ 表示从位置 $u$ 开始，应用道路序列 $A_l, \dots, A_r$ 后的最终位置

合并操作（pushup）：

for (int i = 1; i <= n; ++i)
    nodes[id][i] = nodes[id<<1|1][nodes[id<<1][i]];

即：$F_{[l,r]} = F_{[mid+1,r]} \circ F_{[l,mid]}$

3. 高效查询

查询区间 $[L, R]$ 从位置 $x$ 出发的结果：

• 如果区间完全包含在当前节点，直接返回存储的函数值
• 否则递归查询，并组合结果

if (qr <= mid)
    return query(left_child, l, mid, ql, qr, pos);
if (ql > mid)  
    return query(right_child, mid+1, r, ql, qr, pos);
return query(right_child, mid+1, r, ql, qr, 
            query(left_child, l, mid, ql, qr, pos));

算法步骤

初始化

build(1, 1, t);  // 构建线段树

每个叶子节点初始化：

• 初始为恒等函数：iota(nodes[id]+1, nodes[id]+n+1, 1)
• 然后应用对应道路的转移：nodes[id][edges[mid].first] = edges[mid].second

查询操作

1 L R S：在区间 $[L, R]$ 上计算从 $S$ 出发的最终位置

更新操作

2 i K：将位置 $i$ 的道路改为 $K$，更新线段树

复杂度分析

• 空间复杂度：$O(N \cdot T)$，但 $N \leq 50$ 可接受
• 构建时间：$O(N \cdot T)$
• 查询时间：$O(N \log T)$
• 更新时间：$O(N \log T)$

由于 $N$ 很小而 $T, Q$ 很大，这种用空间换时间的策略非常有效。

算法优势

1. 高效查询：$O(\log T)$ 时间回答任意区间查询
2. 支持修改：$O(\log T)$ 时间更新单点
3. 精确计算：直接存储完整函数，避免近似误差
4. 模块化设计：线段树结构清晰，易于实现

适用场景

这种函数复合线段树适用于：

• 状态转移系统的区间查询
• 函数复合的高效计算
• 小状态空间，大操作序列的问题

样例验证

对于样例1：

• 道路4：$2 \to 5$
• 道路2：$3 \to 2$（但对位置5无效）
• 道路5：$5 \to 1$
• 查询 $[3,5]$ 从2出发：$2 \xrightarrow{4} 5 \xrightarrow{2} 5 \xrightarrow{5} 1$

代码通过线段树正确计算了这个函数复合过程。

---

这种巧妙地将函数复合与线段树结合的方法，成功解决了大规模道路序列的查询与更新问题。