P2617 题解

Gold14526 · 2026-01-17 00:29:53 · 题解

单根号分块做法可以空间线性。

首先离散化，接下来默认值域大小为 V=n+q。

按 \sqrt{q} 操作分块再按 \sqrt{V} 值域分块，可以对于操作块内每个询问记录下每个值域块中有多少在询问区间中的值，这样可以求出答案在哪个值域块里。

接下来只需对每个询问求出这个值域块内每个值的数量，即 O(q) 次单点修改，O(q\sqrt{V}) 次查询区间某个数个数。

可以对每种数分别做，用 O(\sqrt{n})-O(1) 平衡单点修改区间求和即可。

事实上上面两个分块都可以使用多层分块，不过无所谓了。

时间复杂度单根号，空间复杂度线性。