algorithm - 如何通过更新解决离线 range-mex 查询？

Question

注意! 我已经在堆栈和其他一些网站上阅读了所有相同的问题。所有这些都是错误的或比 TL 更有效。

现在关于任务:

输入数组的大小:N <= 5*10^5 and 0 <= array[i] <= N

(数组大小小于等于5*10^5，每个元素小于等于数组大小)

查询:Q <= 2,5*10^5

我们必须将查询(l r)回答为MEX-function在范围内 [l, r]输入数组或继续查询(p x)作为array[p] = x

希望，你能帮我一些想法)

Answer 1

• 将数组分成大小为 n^2/3 的 block 。这将为我们留下 n^1/3 个 block 。
• 对于每对 x y block ，x < y，记录出现在 arr[x * n^2/3...y * n^{2 范围内的每个数字/3}] 然后用缺失的数字做一个集合。有 n^2/3 个这样的对，计数是 O(n)，使得集合是 O(n log n) => O(n^5/3 * log n)
• 对于更新，我们将更新位置在范围内的所有 block 对。更新包括从当前值的计数中减 1，如果计数变为 0，则将值添加到集合中，然后将新值的计数加 1 并从集合中删除该值。这是每对 block 的 O(log n)，这为我们提供了每次更新的 O(n^2/3 * log n) 成本。
• 对于查询，找到完全包含在查询范围内的最大块对。然后查看左右边界缺失的数组值，并对它们进行排序。通过这个 + 缺失值集，我们可以计算范围的 mex。请注意，我们必须向左和向右检查至多 2n^2/3 个值，因此排序的成本为 O(2n^2/3 * log 2n ^2/3).这是每次查询的成本。

总而言之，复杂度为 O(n^5/3 * log n + u * n^2/3 * log n + q * 2n^2/3 * log 2n^2/3) 其中 q 是范围查询的数量，u 是更新的数量。

一些优化:

• 对于更新，您可以使用惰性更新，让范围知道我们需要进行更新，但仅在查询需要时对一对 block 进行更新。