自动搬运

查看原文

来自洛谷，原作者为

	Yonder Morose Dreamer

搬运于2025-08-24 23:09:14，当前版本为作者最后更新于2025-01-13 12:09:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

考虑最值分治，当然也可以用笛卡尔树，这两个东西本质一样。

以下内容视 $n,V$ 同阶。

先考虑 $50$ 分的做法：

假设当前分治的区间为 $x\sim y$，令 $x\sim y$ 最大的 $a_i$ 为 $a_k$。枚举小的一边（这里只讨论枚举左边，右边的同理），这时固定了 $b_l,a_k$，变为求 $m$ 次：$k\sim r$ 中 $b_l\equiv b_i\pmod{a_k}$ 的 $i$ 的个数。存成 $m$ 个询问，形如 $l,r,x,y$，求 $l\sim r$ 中模 $x$ 为 $y$ 的 $b_i$ 的个数。

根号分治跑询问即可，时间复杂度 $O(n\sqrt n\log n)$。

对于 $100$ 分的做法：

思考为什么最值分治枚举小的一边时间复杂度是 $O(n\log n)$。因为其对左区间长度与右区间长度取了最小值，这题也可以考虑这么优化。

假设当前分治区间短的一边的长度为 $q$，对短边跑根号分治的时间复杂度为 $O(q\sqrt V)$。若 $q\sqrt V>n$，显然不如暴力枚举另一边，那么就有：$T(n)=\displaystyle\max_{2k\le n}\{T(k-1)+T(n-k)+\min\{k\sqrt V,n\}\}$，可得 $T(n)=O(n\sqrt V)$。

时隔多日后补个证明，别打我。

令 $u=\frac{n}{\sqrt V}$（这是函数内的 $n$）。

把 $T(n)$ 拆成（以下所有内容，默认 $2k\le n$）：

$$T(n)=\max\{\displaystyle\max_{k\le u}\{T(n-k)+k\sqrt V+\frac{k(k-1)}{2}\},\displaystyle\max_{k\ge u}\{T(k-1)+T(n-k)+n\}\} $$

考虑从其中弄出两个函数：

$$A(n)=\displaystyle\max_{k\le u}\{A(n-k)+\frac{k(k-1)}{2}+k\sqrt V\} $$$$B(n)=\displaystyle\max_{k\ge u}\{B(n-k)+B(k-1)+n\} $$

对于 $A(n)$ 绝对是 $k$ 越大越好，于是 $k=u$，易证 $A(n)=O(n\sqrt V)$。

易证 $A(n)=B(n)$。

考虑从 $1\to n$ 计算 $T(n)$，对于 $n\le\sqrt V$ 有：$T(n)=A(n)=B(n)$。

考虑代入法：

$$T(n)=\max\{\displaystyle\max_{k\le u}\{A(n-k)+k\sqrt V+\frac{k(k-1)}{2}\},\displaystyle\max_{k\ge u}\{B(k-1)+B(n-k)+n\}\}=\max\{A(n),B(n)\}=O(n\sqrt V) $$

终于结束啦。