P11365 [Ynoi2024] 新本格魔法少女りすか 题解

考虑序列分块，设块长为 $B$。朴素地设 $f_{i,j}$ 表示前 $i$ 个块对前 $j$ 个数的贡献空间会炸，注意到贡献独立，考虑离线逐块处理。

现在我们希望求出一个块 $(l,r,id)$ 对所有询问的所有贡献，只需要预处理值域前缀和以及贡献到前缀数的前缀和即可 $O(\sum m_i)$ 做掉。注意防止算重要用一些小技巧。复杂度 $O(\frac{n\sum m_i}{B})$。

剩下所有散块，顺次加入 BIT 暴力查询即可，复杂度 $O(B\log n\sum m_i)$。

平衡复杂度即可做到 $O(\sqrt{n\log n}\sum m)$，非常卡常，可能需要更快的 BIT 和一些清空技巧。

代码按照传统不放。