CF765F Souvenirs

M1rac0 · 2022-11-30 13:18:40 · 题解

CF765F Souvenirs

先观察题目要求：静态区间查询，不强制在线。由此想到使用莫队来解决本题。

容易发现，将一个子串排序后，其答案的候选项只有相邻两项之差。最暴力的方式是用 multiset 来维护查询区间内的所有数。最后更新答案需要遍历整个 multiset，时间复杂度为 O(nm)，肯定过不了。

考虑在扩展莫队区间的同时更新答案。由于更新答案的方式是取最小值，撤销时难以处理，需要用到回滚莫队。时间复杂度为 O(n \sqrt{m} \log{n})，也过不了。代码，TLE on #13。

由于插入的数一定是 a 中的某一项，最多只有 n 个不同位置，于是可以把 a 离散化（即获取排名）后用 bitset 维护莫队区间。具体地，若 a_i 在本次查询的区间内，则令 bitset 中其排名的相应位置为 1。利用 _Find_next 函数可以找到后继 1 的位置。若是要找前驱 1，另开一个 bitset 记录倒序的信息，然后 _Find_next 即可。这个做法时间复杂度为 O(\frac{n^2\sqrt{m}}{w})，跑得挺快，但是仍然过不了。代码，TLE on #37。

让我们来思考一下这个做法的瓶颈。对于一个长度为 l 的 bitset，每次 _Find_next 的时间复杂度为 O(\frac{l}{w})，这个做法每次需要 O(\frac{n}{w})，太费时间。可不可以让 l 小一些？当然可以！对于排名的值域再进行分块，扩展莫队区间时仅在一块中更新答案，回滚之前再用 _Find_first 函数（返回 bitset 中第一个 1 的位置）更新块间答案。值域块长取 \sqrt{n} 时较快，时间复杂度为 O(\frac{nm}{w})，但是常数极小，根本跑不满，能过。代码，Accepted。

还有一些说明：

• 上面的文字结合相应代码来阅读更容易理解。
• 值域块长 l 设定为 \sqrt{n} 没有什么依据，但是可以过，换一个数可能过不了。使用严谨的数学推导求最优块长对于这个做法并不适用，毕竟 _Find_first 和 _Find_next 的时间复杂度太玄学了。
• 离散化的时候不要去重，否则答案为 0 时不好处理。
• 对于值域分块，更新块间答案的时候不能只考虑相邻的两个 bitset，有可能隔着几个空的 bitset 更新答案。
• 注意空间的问题，不要把 bitset 开太大，否则清空会很费时间。