题解 P1903 【[国家集训队]数颜色 / 维护队列】

## 大家好， 蒟蒻小Jf很喜欢分块， 于是就说一下时间为 (n+m) sqrt (n) 空间为线性的在线分块做法吧qwq 首先n^(5/3)的暴力分块应该不难想， 设块大小为T，维护每两个块之间的答案ans，再维护一下cnt（i, j）表示前i个块中j这个数出现的次数。 查询时可以在T的时间内完成散块的信息统计； 然后修改的时候暴力修改（n/T）^2的ans。 当T取到n^(2/3)的时候复杂度为n^(5/3)。 这个东西显然不如带修莫队， 所以要对其进一步进行优化。 ### 优化方案： 考虑到修改ans的复杂度是接近On级别的， 且不是很好优化， 所以考虑用多个修改操作来平摊这个复杂度(定期重构） 具体做法是先预处理出每两个块中的答案， 然后用vector存一下每个数每次出现的位置， 每个位置是这个位置上的数在序列中第几次出现的。 这两个信息都是n级别的。 > 对于不超过sqrt次修改， 查询的时候可以直接分类讨论一下得到答案。 > 每sqrt次修改就需要重构一下。 设每个修改的位置是posnow， 这个颜色前一次出现的位置是posx， 后一次出现的位置是posy。 答案数组是ans 那么变化的只有b[posx] < i <= b[posnow] 且 b[posnow] <= j < b[posy] 的 ans(i, j)信息。 这个东西可以把ans数组放在二位平面里差分一下（一维是i一维是j， 两个维度的大小都是sqrt级别的）。 单次差分的复杂度就是sqrt n， sqrt次就是On， 然后再用O(sqrt*sqrt)扫一遍差分数组, On重新处理一下vector就能完成重构了。 这样最多重构sqrt (m) 次， 总复杂度就是 (m+n) sqrt (n) 那么到这里就讲完啦。 还有什么不明白的就私信小蒟蒻吧>_<