自动搬运

查看原文

来自洛谷，原作者为

	zjy2008 else if

搬运于2025-08-24 23:06:45，当前版本为作者最后更新于2024-12-16 19:44:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现这个题和P8984很像，考虑那个题的做法。记 $f_{n,k}$ 为序列长度为 $n$，查询时加法次数为 $k$ 时修改至少要 $f_{n,k}$ 次加法。根据那个题，我们有：

• $k=0$：显然直接处理出所有区间和，具体值可以解方程。
• $k=1$：考虑猫树，记 $mid=(l+r)/2$，预处理出所有 $[i,mid)$ 和 $[mid,i)$ 的区间和，然后可以递归两侧做子问题。（注意你可能需要特判端点）
• $k>1$：考虑设置 $c$ 个关键点，相邻之间夹了 $b$ 个点，在仔细考虑每个端点如何处理之后可以得到 $3$ 种子问题：两端 $(len,k)$，块内 $(b,k)$，块间 $(c-1,k-2)$。于是直接转移即可。

直接枚举 $b,c$，这样我们得到了一个时间复杂度 $O(n^2k\log)$ 的做法。发现 $(n,M_2)$ 只有 $8$ 种，手动跑出最外层的 $b,c$ 即可通过。

放一份没有最外层剪枝的代码。