请告诉我Range Mex查询的高效算法 [英] Please tell me the efficient algorithm of Range Mex Query

问题描述

我对此问题有疑问。

问题

• 为您提供了一个序列 a [0]，a 1]，...，a [N-1] 和范围（l [i]，r [i]）（0< = i< = Q-1）。


• 计算 mex（a [l [i]]，a [l [i] + 1]，...，a [r [i]-1]） $ c>（l [i]，r [i]）。

• You are given a sequence a[0], a 1],..., a[N-1], and set of range (l[i], r[i]) (0 <= i <= Q - 1).
• Calculate mex(a[l[i]], a[l[i] + 1],..., a[r[i] - 1]) for all (l[i], r[i]).

函数mex最小排除的值。

维基百科mex函数页面

The function mex is minimum excluded value.
Wikipedia Page of mex function

您可以假定 N <= 100000，Q <= 100000，a [i] <= 100000 。

O（N *（r [i]-l [i]）log（r [i]-l [i]））算法很明显，但是效率不高。

You can assume that N <= 100000, Q <= 100000, and a[i] <= 100000.
O(N * (r[i] - l[i]) log(r[i] - l[i]) ) algorithm is obvious, but it is not efficient.

我当前的方法

#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）很慢。请告诉我更快速的算法。

O(N^2) is slow. Please tell me more fast algorithm.

推荐答案

这是一个 O（（Q + N）log N） 解决方案：

1. 让我们从左到右遍历数组中的所有位置并存储最后一个分段树中每个值的出现次数（分段树应在每个节点中存储最小值）。

1. Let's iterate over all positions in the array from left to right and store the last occurrences for each value in a segment tree (the segment tree should store the minimum in each node).

添加 i 个数字，我们可以回答所有右边界等于 i 的查询。

After adding the i-th number, we can answer all queries with the right border equal to i.

答案是最小值 x ，使得 last [x] < l 。我们可以从根目录开始向下查找分段树（如果左子目录中的最小值小于 l ，则转到那里。否则，请转到右边）儿童）。

The answer is the smallest value x such that last[x] < l. We can find by going down the segment tree starting from the root (if the minimum in the left child is smaller than l, we go there. Otherwise, we go to the right 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)

查找较小的函数像这样：

The find smaller function goes like this:

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 函数，我敢肯定，对于给定的方法，它足够快约束。

This solution is rather easy to code (all you need is a point update and the findFisrtSmaller function shown above and I'm sure that it's fast enough for the given constraints.

这篇关于请告诉我Range Mex查询的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！