题目题解：追忆 (Recall)

题目大意

给定一个有向图，每个节点有两个权值 $a_i$ 和 $b_i$，且这两个权值序列都是 $1 \sim n$ 的排列。需要支持三种操作：

1.交换两个节点的 $a$ 权值

2.交换两个节点的 $b$ 权值

3.查询从节点 $x$ 可达且 $a$ 权值在 $[l,r]$ 范围内的节点中，$b$ 权值的最大值

算法思路

核心思想

本题采用离线处理 + 标签传播 + 线段树的混合算法：

1.标签预处理：为每个节点计算入标签和出标签，压缩可达性信息

2.操作离线处理：将动态操作转化为静态问题

3.线段树维护：高效处理区间最大值查询

算法标签

• 图论 (Graph Theory)

• 广度优先搜索 (BFS)

• 离线算法 (Offline Algorithm)

• 线段树 (Segment Tree)

• 剪枝优化 (Pruning Optimization)

详细步骤

1. 标签计算

void pruned_bfs(int s) {
    // 计算从s出发能到达的节点（出标签）
    // 计算能到达s的节点（入标签）
    // 使用剪枝避免重复计算
}

• 出标签 lb[u][0]：记录从u出发能到达的关键节点

• 入标签 lb[u][1]：记录能到达u的关键节点

• 剪枝策略：如果通过已有标签能推断出可达性，则停止BFS扩展

2. 评分函数

score[i] = (ll)(g[i].size() + 4) * (rg[i].size() + 1);

根据节点的出度和入度计算重要性评分，优先处理重要节点。 3. 离线处理流程 1.预处理阶段：计算所有节点的标签

2.操作记录阶段：

• 对于修改操作，记录权值变化

• 对于查询操作，关联到相关标签

3.批量处理阶段：按重要性顺序处理所有操作

4. 线段树维护

struct Seg {
    int tr[N << 3];
    void modify(int p, int s, int t, int x, int y); // 单点更新
    int query(int p, int s, int t, int l, int r);   // 区间最大值查询
};

复杂度分析

• 预处理：$O(n \cdot \text{avg-label-size} \cdot \log n)$

• 每次操作：$O(\log n)$

• 空间复杂度：$O(n \log n)$

其中 $\text{avg-label-size}$ 是平均标签大小，通过剪枝控制在合理范围内。

关键优化

1.标签压缩：用少量关键节点表示可达性关系

2.重要性排序：优先处理高评分节点提高效率

3.操作批处理：减少线段树更新次数

4.内存复用：使用bitset和及时清空避免内存浪费

代码特点

• 使用面向对象封装线段树和访问标记

• 采用RAII思想管理内存

• 输入输出优化处理大数据

• 模块化设计便于调试

该算法通过巧妙的标签设计和离线处理，在保证正确性的同时，有效降低了时间复杂度，能够处理$10^5$级别的数据规模。