洛谷 P11831 [省选联考 2025] 追忆

前置知识

• 链式前向星存图
• 拓扑排序
• bitset 的基本用法
• 卡常基本技巧

题意

给你一张 $n$ 个点 $m$ 条边的有向无环图。编号为 $i$ 的点有两个权值 $a_i$，$b_i$。$a$ 和 $b$ 都是 $1$ 到 $n$ 的排列。共有 $q$ 次操作，操作共有三种。

1. 给定 $x$，$y$，交换 $x$ 号点和 $y$ 号点的 $a$ 权值。
2. 给定 $x$，$y$，交换 $x$ 号点和 $y$ 号点的 $a$ 权值。
3. 给定 $x$，$l$，$r$，找出 $x$ 能够到达且 $a$ 权值在 $[l,r]$ 的点中，$b$ 权值的最大值。

多组数据。

数据范围：$T\le3$，$n\le 10^5$，$m\le 2\times 10^5$，$q\le 10^5$。

时间限制 9.00s，空间限制 2.00GB。

做法

首先使用 bitset 求出每个点能到达的点的集合。

然后我们维护一个 $mp_i$ 表示 $b$ 权值为 $i$ 的点的编号。

每一次查询，从大到小遍历 $i$，如果 $mp_i$ 在 $[l,r]$ 范围内且 $x$ 能到达 $mp_i$，则 $i$ 就是答案，结束循环。

每一次修改，如果是改 $a$，直接交换 $a_x$ 和 $a_y$。如果是改 $b$，交换完 $b_x$，$b_y$ 后还需要交换 $mp_{b_x}$，$mp_{b_y}$。

这样就能得到60分。（查询暴力遍历是20分）

卡常

• 首先这道题不需要开 long long，所以删掉 #define int long long。

• 然后链式前向星在 DAG 或树中比 vector 存图更加优秀 （同 P9755 [CSP-S 2023] 种树）

• 交换两个变量时，使用 swap(a,b) 似乎比a^=b,b^=a,a^b 更优？？实际测试中是这样的。

• 关同步流，只使用 getchar，putchar 和 puts

然后就过了。

可能有评测姬波动，多交几发。