P5609
zhylj
·
·
题解
大家好，我非常喜欢暴力数据结构，于是我用分块 A 了这道题。
（其实一部分思想是相同的，不过该做法可以做到线性空间）
先考虑最简单的分块，将序列分成 \dfrac nB 块，每块大小为 B，对于每个块 ，望能对于所有的 x，计算出如果初始的 result 为 x，在对所有块中的元素 a_j 依次进行了 result = ModAdd(result, a[j], p) 之后，result 会是什么。为了解决这个问题，我们先引入一个引理：
引理：对于一个序列 a_1,a_2,\cdots,a_n，记 x_i 表示最小的 x，使得初始的 result 为 x 时，ModAdd 函数减去 p 的次数大于等于 i。则 x_1\le x_2\le \cdots\le x_n。
证明：考虑某个前缀 a_1,a_2,\cdots,a_i 被减去 p 的次数 t_i，再记 s_i = \sum_{j\le i} a_i，则我们要求满足如下条件的最大的一组 t_1,t_2,\cdots,t_n：t_i\le t_{i+1}\le t_i + 1，且若 t_i\neq t_{i+1}，则必有 s_i\ge t_ip。注意到改变初始的 x 只会导致限制变松，所以成立。
于是我们希望对所有块 b，求出 f(b,i) 表示对于这个块的元素，最小的初始 result，使得 ModAdd 函数减去 p 的次数大于等于 j，这样在询问的时候就可以通过二分查找来一次跳过一个块了，再结合边角块暴力，我们就可以在 \mathcal O\left(B+\dfrac nB\log n\right) 的时间内完成询问了。
对于如何求 f(b,i)，我们考虑分治，假如我们以及求出了 [L,\mathrm {mid}]，(\mathrm {mid},R] 的 f，现在欲求 [L,R] 的 f，考虑对 i 从小到大依次求出 f(b,i)，再维护两个指针 j,k 表示当前时刻 i 的边界对应着的左半边和右半边。当我们每次令 i\gets i + 1 时，考虑如何计算新的 j,k，我们先 Check 是否可以不改变 j，这样由于减去 p 的个数不变，所以当前的 j,k 对应的初始值 x 是随着 k 增大而增大的，我们只需 Check k+1 是否满足条件，否则 j 变为 j+1，由于 j+k 必须等于 i，此时 k 必须保持不变。我们每次的 f(b,i) 即为此时的 j,k 分别对应的初始的 x 的最大值。于是我们可以在 \mathcal O(B\log n) 的时间内对一个块进行预处理，所有的块总共的预处理时间复杂度为 \mathcal O(n\log n)。
当 B=\sqrt {n\log n} 时，时间复杂度最小，为 \mathcal O(n\log n+m\sqrt {n\log n})，并没有办法通过此题。
考虑如何优化，这是一个被我神仙同学 jbc 独立发明的 trick，不知道还有没有别的题，我们不妨叫它 jbc 树：
我们注意到一个事实，预处理所有的块的时间复杂度其实与块长无关，所以我们考虑多预处理几种块长，例如，我们预处理 B 和 \sqrt {nB} 的块长，那么对于一个询问，我们可以拆分成至多两段不超过 B 的散块，至多两段分别不超过 \dfrac{\sqrt {nB}}{B}=\sqrt {\dfrac nB} 个大小为 B 的块，至多一段不超过 \dfrac {n}{\sqrt {nB}}=\sqrt {\dfrac nB} 个大小为 \sqrt {nB} 的块，而最前者处理的复杂度为 \mathcal O(B)（直接暴力扫），后两个处理的复杂度都为 \mathcal O\left(\sqrt {\dfrac nB}\log n\right)，所以当 B = n^{\frac 13}\log^{\frac 23} n 时，询问的时间复杂度最小，为 \mathcal O(n\log n + mn^{\frac 13}\log^{\frac 23}n)，可以轻松通过本题，并且常数较小，且做到了 \mathcal O(n) 的空间。
代码：剪贴板链接（11.76s / 34.19MB）。
事实上，如果我们划分了 k 层，那么不难发现时间复杂度为 \mathcal O(kn\log n+kmn^{\frac 1k}\log^{\frac{k-1}k}n)，由于后面处理起来比较麻烦，我们不妨放大为 \mathcal O(kn\log n+kmn^{\frac 1k}\log n)，注意到前者为增函数，后者为减函数，记 k=\log_an，则有原式为 \mathcal O(n\log_an\log n+ma\log_an\log n)，前后两项之比为 \dfrac {n}{ma}，当 a=\dfrac {n}m 时复杂度最小，为 \mathcal O(n\log_{n/m}n\log n)，实际上是比线段树多个 \log 的。