Luogu5397 [Ynoi2018] 天降之物

第四分块。

题意：维护序列 ，支持：

• 将所有的 替换为 。

• 给出 ，找到 ，使得 最小。或指出这样的 不存在。

强制在线，输入中的所有数均在 内，时限 ，空限 。

---

根号分治。

• 无修改

记 的出现次数为 。

称 为大数（共 个），否则为小数。

预处理大数 与所有其他数之间的答案 。这显然可以枚举 后 完成。

若询问时 有一个是大数，则查表。

否则把 的出现位置合在一起排序，每个点只需要找前驱后继即可。

需要先预处理每种数位置的有序序列，这样就只需要归并了。

我们已经得到了一个严格 的静态根号分治做法。

到此为止这还是个紫牌题，接着考虑修改。

• 原问题

将 修改成 也可以在维护映射之后看做将 修改成 ，所以可以认为在修改操作中总有 。

修改时，若 均为大，则暴力计算 个和两者相关的所有询问。这样的合并最多发生 次，故复杂度为 。

若 均为小，将两者的出现位置归并即可，若大小超过 则按照大数暴力预处理。

若 为小， 为大，直接合并复杂度是错误的，但可以知道， 的大小总和是 的。

进一步进行根号分治，对于一个大数，维护一个附属数 。实际上两个数是一样的，但不合并。

每次将 与附属数合并，若附属数变为大数，则与 合并。

这样，就转化成了小小合并以及大大合并，复杂度仍为 。

每次合并后要将 中的一些贡献合并。

查询时，若 为大数，则分别查询 之间的贡献，以及 之间的贡献。没有增大复杂度。