自动搬运

查看原文

来自洛谷，原作者为

	CXY07 It's my fiesta.

搬运于2025-08-24 22:33:18，当前版本为作者最后更新于2021-08-20 20:00:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

本题解同步发布于 My Blog

题意：

给定长度为 $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})$。代码先不放了 因为本人还没卡过