一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

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

posted on 2019-05-27 17:43:24 | under 题解 |

大家好, 蒟蒻小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)

那么到这里就讲完啦。 还有什么不明白的就私信小蒟蒻吧>_<