啤酒旧山衣

chenxia25 · 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).