题解：P10151 [Ynoi1999] SMV CC-64“蝰蛇”

Otomachi_Una_ · 2024-09-19 22:19:28 · 题解

显然维护每个极长的合法段，这是因为每次修改只会进行 \mathcal O(1) 次合法段的合并或分裂。

考虑怎么维护存在 a_i=x 这个条件。首先容易对询问 l,r 的两端点进行特判。

考虑怎么搞中间那些极长段，我们来用上环的这个条件。沿着 b 的置换环进行编号。不难发现在这样的编号下一个极长合法段拥有的 \{a_i\} 集合是不超过两段区间的并。

搞个线段树套平衡树，对每个极长段给每个能覆盖到的 a_i 打个标记。查询只需要查询包含 x 的极长连续区间的长度的 max 即可。

上述都能用 FHQ 轻松维护。

不卡常。