Luogu6019 [Ynoi2010] Brodal queue

题意 ： 维护一个长为 的序列 ，支持：

• 区间覆盖。

• 给出 ，查询有多少二元组 满足 且 。

强制在线，，时限 ，空限 。

---

感谢 @mrsrz 的指导。

记 为 的出现次数，则贡献为 。于是只需计算区间内每种数出现次数的平方和。

询问

对于纯色的块，当做散块元素进行特殊处理。

把贡献分为三类 ： “散块+纯块内部”，“散块+纯块 与 非纯块之间”，“非纯块 内部”。

散块+纯块的颜色种类数是 的。

• 散块+纯块 内部

  容易用桶暴力计算。

• 散块+纯块 与 非纯块之间

  记 前 个（只考虑非纯块贡献）块内 出现的次数。

  记整块区间为 。

  对于元素 ，在散块+纯块中出现了 次，则贡献为 。

• 整块内部

  记 。

  块 之中的贡献为 。

修改

考虑如何维护 。

对于散块，暴力重构。

对于整块，若不是纯色块，暴力重构，若是，则简单打标记。

不难发现，每次对块的暴力重构都会导致分界线减少至少 个，每次修改只会增加 条分界线，于是总复杂度为 。

将一次修改描述为“将颜色 在块 中的出现次数增加了 ”。

这样的修改的总次数是 的。

每次在 上重新做一次前缀和，复杂度为 。

对于 ，考虑 。

• ：变化量为 。

• ：变化量为

• ：变化量为

对 的增量维护两个方向的差分。对于 ，用 维度的划分处理，对于 用 维度的差分处理。

修改复杂度容易做到 。单点查询时只需将两个方向的贡献更新，也是 。

综上，时空复杂度 。