algorithm - 带有更新的 MEX 查询

您可以使用Segment tree数据结构和复杂性O(nlogn + qlogn)。如果您不熟悉Segment tree，最好收集有关它的知识。你会在网上找到很多关于它的资源。

在段树中，通常每个节点都保存有关特定范围的信息。通常，叶节点保存有关特定数组索引的信息，内部节点从其左右子节点生成或更新信息。

A考虑这些情况下未出现在 range中的最小正整数[l, r]：

对于 {2,3}，答案是 1（1 是最小的正整数）。
{1,2} 的答案是 3
{1,4,2} 的答案是 3

对于答案为 1 的情况：

如果范围内的最小值大于 1，则答案为 1。为此构建一个段以查找该特定范围内的最小值。见下图：

从上图中我们可以看出，叶子节点保存了特定的数组索引值，内部节点根据它的左右子值（min(left child's min value, right child's min value)）更新它的值。从此段中，我们可以找到中任何范围的最小值O(logn)。如果任何数组索引值发生变化，我们可以更新O(logn).

对于答案为（范围的最大值）+1 的情况：

为此，构建一个细分以查找此特定范围内的最大值。它类似于上面的段树，而不是找到最小值，我们将找到最大值。

对于答案既不是 1 也不是（范围的最大值）+1 的情况：

对于这种情况，我们将需要一个段树，它将给出大于范围最小值[l,r]且小于范围最大值的最小缺失正值[l,r]。我们将使用 value0来表示此范围内没有缺失值[l,r]。对于叶节点，我们将缺失值设置为0。现在我们将如何计算内部节点的缺失值。假设对于一个内部节点P，我们将计算缺失值。P有左孩子L和右孩子R。的缺失值P将使用以下程序计算：

P.Missing_Value = infinite value
// for the case L = {1,2} , R = {4,5}
if L.Max_Value+1 < R.Min_Value {
  P.Missing_Value = min(P.Missing_Value, L.Max_Value + 1)
}

// for the case L = {4,5} , R = {1,2}
if R.Max_Value+1 < L.Min_Value {
  P.Missing_Value = min(P.Missing_Value, R.Max_Value + 1)
}

// for the case L = {1,3} , R = {1,3,4,5} or L = {1,3} , R = {4,5} or L = {3,5} , R = {1,2}
if L.Missing_Value != 0 && (L.Missing_Value < R.Min_Value || L.Missing_Value > R.Max_Value || L.Missing_Value == R.Missing_Value) {
  P.Missing_Value = min(P.Missing_Value, L.Missing_Value)
}

// for the case R = {1,3} , L = {1,3,4,5} or R = {1,3} , L = {4,5} or R = {3,5} , L = {1,2}
if R.Missing_Value != 0 && (R.Missing_Value < L.Min_Value || R.Missing_Value > L.Max_Value || R.Missing_Value == L.Missing_Value) {
  P.Missing_Value = min(P.Missing_Value, R.Missing_Value)
}

// if there is no missing value
if P.Missing_Value == infinite {
  P.Missing_Value = 0
}

敲定

首先检查 ans 是否可以为 1。
如果 ans 不能为 1，则检查缺失值。
如果未找到缺失值，则 ans 将最大值 + 1。

上面的树将是您的最终段树。从这里您可以查询任何范围的最小值、最大值和缺失值。这些查询和更新（如果数组索引值更改）将占用O(logn).

关于段树的一些教程/资源：

algorithm - 带有更新的 MEX 查询

问题描述

解决方案

推荐阅读