P11365 [Ynoi2024] 新本格魔法少女りすか 题解
Reunite
·
·
题解
考虑序列分块，设块长为 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 和一些清空技巧。
代码按照传统不放。