自动搬运

查看原文

来自洛谷，原作者为

	chenxia25 Всё ж старается не зря...

搬运于2025-08-24 22:53:07，当前版本为作者最后更新于2023-12-19 17:04:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到 $a > 0$, 也就是 $A$ 总是不降的, 所以我们只需要快速地模拟 $A$ 从 $0$ 增加到超过 $\max r$ 的过程, 此后 I 类语句的跳转也就固定了, 只要简单地判环即可.

现在我们来考虑如何快速地模拟 $A \leq \max r$ 的过程. 先考虑 $\sum \max r \leq 10^5$ 的子任务, 这就是说我们可以对每个 $A_0 \in [0, \max r]$, 都去处理 $A = A_0$ 的时间段. 在 $A = A_0$ 固定时, 所有的 I 类语句的跳转也是固定的, 如果能够快速知道在当前局面下遇到的第一个 A 类语句 (或陷入循环), 问题便迎刃而解. 容易想到用并查集维护: 对跳转类语句进行连边, A 类和 E 类不连边, 并查集可以得到从某个点出发一直沿唯一的出边走会停在哪里 (再记录加边失败的信息即可判环). 而 I 类语句的贡献可以拆成 $A_0$ 所在的三个区间, 每个区间内的连边情况是固定的, 使用线段树分治 + 可撤销并查集 (按秩合并优化) 即可. 时间复杂度 $\mathrm O(n + \max r \log n \log \max r)$.

再来考虑正解. 虽然不再能对每个 $A_0 \in [0, \max r]$ 依次处理, 但注意到所有 I 类语句的跳转情况只有不超过 $2n$ 种本质不同的局面, 且对应 $A_0$ 的不超过 $2n$ 个区间, 于是考虑对每个区间依次处理, 求出在哪行进入下一个区间 (或陷入循环), 以及在过程中 $A$ 增加了多少. 注意到任意局面下跳转情况是一个基环树和树的混合森林, 考虑用 LCT 维护 (对于基环树, 随意断掉环上的一条边), 在链所对应的 Splay 上二分即可. 对于基环树的没有被加入的那些条边, 采用懒惰加入法, 即加入失败 (成环) 的时候就不加, 等到在 LCT 上跳到未将出边加入到 LCT 的跳转语句节点时再加入. 这样每条语句至多被加入 $\mathrm O(1)$ 次, 由势能分析法可知总复杂度为 $\mathrm O(n \log n)$.