自动搬运

查看原文

来自洛谷，原作者为

	Kuristina 忘れないで，あなたはどの世界線にいてもひとりじゃない，私がいる

搬运于2025-08-24 22:43:51，当前版本为作者最后更新于2023-03-13 10:00:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

问题概述：

本题中，给定长度为 $n$ 的序列 $a$，进行 $q$ 次操作，分为两种：

1. 查询操作：对于查询操作，需要在区间 $[l,r]$ 内找到值在 $[a,b]$ 范围内出现次数为偶数的最大数的后继。
2. 修改操作：对于修改操作，需要将 $a_i$ 的值修改为 $x$。

解题思路：

本题需要实现查询和修改两种操作，其中查询操作需要找到值在指定区间内出现次数为偶数的最大数的后继。因此，可以采用带修莫队算法和值域分块的思想来解决这个问题。

具体的实现细节如下：

• 首先，将序列 $a$ 分成 $B$ 个块，每个块的大小为 $n/B$。
• 对于每个块，需要记录区间内每个元素的出现次数，并统计出现次数为偶数的最大值。
• 对于查询操作，可以采用带修莫队算法。具体来说，可以先将所有的查询操作按照左端点所在块的编号排序，对于同一个块内的查询操作，按照右端点排序。这样，可以保证同一个块内的查询操作按照右端点的顺序依次处理。
• 在处理每个查询操作时，需要先将修改操作同步到当前查询操作的时间戳。然后，可以采用类似于普通莫队算法的方式，在块内和块之间进行查询。
• 在块内查询时，可以直接遍历该块内的所有元素，并统计出现次数为偶数的最大值。
• 在块之间查询时，需要统计出现次数为偶数的最大值，并找到值最大的元素。这个过程可以通过预处理每个块的出现次数为偶数的最大值来完成。
• 对于修改操作，需要在块内进行修改，并更新块的出现次数为偶数的最大值。

取 $B = \sqrt n$，带修莫队 $O(n^{5/3})$。至此，我们用非常波特的方式解决了这道波特题目。