自动搬运

查看原文

来自洛谷，原作者为

	a___ 这个家伙很蒻，什么也没有留下qwq

搬运于2025-08-24 22:29:49，当前版本为作者最后更新于2021-04-08 16:34:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分块。

设每块大小为 $S$，将 $n$ 个玩具分成 $\dfrac nS$ 块。
设 $f_{l,r,x}$ 表示仅所有在 $[1,l]\cup[r,\dfrac nS]$ 块内的玩具可售时编号为 $x$ 的小朋友愉悦度的最大值。
我们从 $1$ 到 $n$ 顺次做背包，每做完一个块就用另一个指针从右向左扫一遍做背包，就可以容易地求出 $f$。
查询 $l,r$ 时先拿来 $f_{belong[l]-1,belong[r]+1}$ 再把 $l$ 所在块内和 $r$ 所在块内暴力加入。

时间复杂度：
修改：$\Theta(\sum n\cdot\dfrac nS\cdot m)=\Theta(\sum\dfrac{n^2m}S)$
查询：$\Theta(\sum q\cdot S\cdot m)=\Theta(\sum qmS)$
总复杂度为 $\Theta(\sum m(\dfrac{n^2}S+qS))$，取 $S=\dfrac n{\sqrt q}$ 时最优为 $\Theta (\sum nm\sqrt q)$。 注意如果用的不是单调队列优化多重背包而是二进制分组的话还要多个 $\log$。

空间复杂度：
$\Theta(\dfrac nS\cdot\dfrac nSm)=\Theta(\frac{n^2m}{S^2})$。

取 $S=\sqrt n$ 时，时间复杂度为 $\Theta(\sum m(n+q)\sqrt n)$，空间复杂度为 $\Theta(nm)$，注意到 $\sqrt n$ 最大只有 $\sqrt{1000}\approx30$，可以通过此题。