【模板】树套树 题解

· · 题解

线性空间分块做法。

显然只需解决前三个操作即可，而且询问 1,2 是独立的。

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

对于询问 1，先对序列分块，逐块处理，只需在值域上维护单点加前缀求和即可，用 O(\sqrt{V})-O(1) 分块平衡一下。

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

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

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

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

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