自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

搬运于2025-08-24 22:55:11，当前版本为作者最后更新于2024-09-19 22:19:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

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

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

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

上述都能用 FHQ 轻松维护。

不卡常。