题解 P7432 [THUPC2017] 钦妹的玩具商店

a___ · 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。

空间复杂度：