题目链接:[JRKSJ R2] 你的名字。

题意:

给定长度为 $n$ 的序列 $\{a_n\}$,共 $m$ 组询问,每次询问一个区间 $[l,r]$ 中,在 $\bmod\ k$ 意义下的最小值。
$1\le n,m\le 3\times 10^5, 1\le a_i\le 10^5$。

受不了了根本卡不动

这题我曾经自己编出来过,但只会 $\mathcal{O}(n\sqrt{n\log n})$。/kk

考虑根号分治。设一个阈值 $V$,分别考虑 $k>V$ 和 $k\le V$ 的询问。

对于 $k\le V$ 的询问,本质不同的 $k$ 只有 $V$ 种。因此可以将其中 $k$ 相同的拿出来一起做。对于一个固定的 $k$,设 $b_i=a_i\bmod k$,使用分块或线段树等 $\mathcal{O}(n)$ 预处理的数据结构进行维护即可。这里的复杂度是 $\mathcal{O}(nV+m\log n)$ 或 $\mathcal{O}(nV+m\sqrt{n})$。

对于 $k>V$ 的询问,考虑到 $a\bmod k=a-ck$,所以考虑枚举 $k$ 的倍数 $ck$,然后寻找一个 $a_i$ 使得 $a_i\ge ck$ 且 $a_i - ck$ 最小。不难发现一个询问会变成 $\mathcal{O}(\dfrac{10^5}{V})$ 个上述问题。这里需要注意一下空间。

考虑将序列中的元素降序排序,所有询问也降序排序,双指针维护,依次将 $\ge k$ 的元素插入序列,然后询问区间最小值即可完成上述问题。

上述问题中,插入只有 $\mathcal{O}(n)$ 次,而询问有 $\mathcal{O}(\dfrac{10^5m}{V})$ 次,因此考虑把插入的复杂度变高些以平衡查询的复杂度。

考虑使用猫树的思想,做到 $\mathcal{O}(1)$ 的查询。但猫树的插入是 $\mathcal{O}(n)$ 的,无法接受。因此先分块,在分块的结构上套一个猫树,每次插入一个元素后更新整块的值,再记录每个块的前缀、后缀 $\min$,就可以做到 $\mathcal{O}(\sqrt{n})$ 的插入,$\mathcal{O}(1)$ 的查询。

因此此部分是 $\mathcal{O}(n\sqrt{n}+\dfrac{10^5m}{V})$。

发现 $V$ 取 $\sqrt{10^5}$ 复杂度达到最优,最后时间复杂度是 $\mathcal{O}((n+m)\sqrt{n}+m\sqrt{10^5})$。代码先不放了 因为本人还没卡过

标签: 分块, 根号分治

添加新评论