请告诉我Range Mex Query的高效算法

Question

我对这个问题有疑问。

问题

给你一个序列 a[0], a 1],..., a[N-1] 和一组范围 (l[i], r[i]) (0 <= i <= Q - 1)。
为所有(l[i], r[i])计算mex(a[l[i]], a[l[i] + 1],..., a[r[i] - 1])。

函数 mex 是最小排除值。
Wikipedia Page of mex function

您可以假设 N <= 100000, Q <= 100000, and a[i] <= 100000.
O(N * (r[i] - l[i]) log(r[i] - l[i]) )算法很明显，但是效率不高

我目前的做法

#include <bits/stdc++.h>
using namespace std;
int N, Q, a[100009], l, r;
int main() {
    cin >> N >> Q;
    for(int i = 0; i < N; i++) cin >> a[i];
    for(int i = 0; i < Q; i++) {
        cin >> l >> r;
        set<int> s;
        for(int j = l; j < r; j++) s.insert(a[i]);
        int ret = 0;
        while(s.count(ret)) ret++;
        cout << ret << endl;
    }
    return 0;
}

请告诉我如何解决。

编辑：O(N^2) 很慢。请告诉我更快速的算法。

Answer 1

让我们以 left-to-right 的方式处理我们的查询和元素，比如

for (int i = 0; i < N; ++i) {
    // 1. Add a[i] to all internal data structures
    // 2. Calculate answers for all queries q such that r[q] == i
}

这里我们有此循环的 O(N) 次迭代，我们希望在 o(N) 时间内更新数据结构并查询当前处理部分后缀的答案。

让我们使用数组 contains[i][j]，如果从位置 i 开始的后缀包含数字 j，则数组 1 否则为 0。还要考虑我们已经分别计算了每个 contains[i] 的前缀和。在这种情况下，我们可以使用二进制搜索在 O(log N) 时间内回答每个特定的后缀查询：我们应该只在相应的 contains[l[i]] 数组中找到第一个零，这正是部分和等于的第一个位置索引，而不是索引 + 1。不幸的是，这样的数组需要 O(N^2) space 并且每次更新需要 O(N^2) 时间。

所以，我们必须优化。让我们用 "sum query" 和 "assignment" 范围操作构建一个二维 range tree。在这样的树中，我们可以查询任何 sub-rectangle 上的总和，并在 O(log^2 N) 时间内为任何 sub-rectangle 的所有元素分配相同的值，这允许我们在 O(log^2 N) 内进行更新] 时间和查询 O(log^3 N) 时间，给出时间复杂度 O(Nlog^2 N + Qlog^3 N)。 space 复杂度 O((N + Q)log^2 N)（以及数组初始化的相同时间）是使用惰性初始化实现的。

UP: 让我们用 "sum" 修改查询在范围树中的工作方式。对于一维树（为了不让这个答案太长），它是这样的：

class Tree
{
    int l, r;           // begin and end of the interval represented by this vertex
    int sum;            // already calculated sum
    int overriden;      // value of override or special constant
    Tree *left, *right; // pointers to children
}
// returns sum of the part of this subtree that lies between from and to
int Tree::get(int from, int to)
{
    if (from > r || to < l) // no intersection
    {
        return 0;
    }
    if (l <= from && to <= r) // whole subtree lies within the interval
    {
        return sum;
    }
    if (overriden != NO_OVERRIDE) // should push override to children
    {
        left->overriden = right->overriden = overriden;
        left->sum = right->sum = (r - l) / 2 * overriden;
        overriden = NO_OVERRIDE;
    }
    return left->get(from, to) + right->get(from, to); // split to 2 queries
}

鉴于在我们的特定情况下，对树的所有查询都是前缀和查询，from 始终等于 0，因此，对 children 的调用之一总是return 一个简单的答案（0 或已经计算出 sum）。因此，我们可以实现一个 ad-hoc 搜索过程，而不是在二分搜索算法中对二维树进行 O(log N) 查询，与此 get 查询非常相似。它应该首先获取左边的值 child （需要 O(1) 因为它已经计算过了），然后检查我们要查找的节点是否在左边（这个总和小于 number of左子树中的叶子）并根据此信息向左或向右移动。这种方法将查询进一步优化到 O(log^2 N) 时间（因为它现在是一个树操作），给出了 O((N + Q)log^2 N)) 时间和 space 的结果复杂度].

不确定此解决方案对于 Q 和 N 直至 10^5 是否足够快，但它可能会进一步优化。

Answer 2

这是一个 O((Q + N) log N) 解决方案：

让我们从左到右遍历数组中的所有位置，并将每个值的最后一次出现存储在线段树中（线段树应存储每个节点中的最小值）。
添加第 i 个数字后，我们可以回答右边框等于 i 的所有查询。
答案是满足 last[x] < l 的最小值 x。我们可以通过线段树从根开始往下找（如果左边的最小值child小于l，我们就去那里。否则，我们就去右边child ).

就是这样。

这是一些伪代码：

tree = new SegmentTree() // A minimum segment tree with -1 in each position
for i = 0 .. n - 1
    tree.put(a[i], i)
    for all queries with r = i
         ans for this query = tree.findFirstSmaller(l)

查找较小的函数是这样的：

int findFirstSmaller(node, value)
    if node.isLeaf()
        return node.position()
    if node.leftChild.minimum < value
        return findFirstSmaller(node.leftChild, value)
    return findFirstSmaller(node.rightChild)

这个解决方案很容易编写代码（您只需要一个点更新和上面显示的 findFisrtSmaller 函数，我确信它对于给定的约束足够快。

请告诉我Range Mex Query的高效算法

Please tell me the efficient algorithm of Range Mex Query

c++

algorithm

game-theory