请告诉我Range Mex查询的高效算法

平方1001

我对这个问题有疑问。

  • 您将获得一个序列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])为所有计算(l[i], r[i])

功能mex是最小排除值。
维基百科的mex功能页面

您可以假设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)是缓慢的。请告诉我更快速的算法。

克拉斯科维奇

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

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

  2. 添加第-i个数字后,我们可以回答所有右边界等于的查询i

  3. 答案是最小的值x,使得last[x] < l我们可以从根目录开始向下查找分段树(如果左子项的最小值小于l,则转到那里。否则,我们去右子项)。

而已。

这是一些伪代码:

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)

find较小的函数如下所示:

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上面显示功能,我相信对于给定的约束它足够快。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

请,有人可以告诉我我的查询出了什么问题吗?当我在注册页面上上传文件时,它说的是错误的查询?

请告诉我何时在Java中使用getInstance()方法。

查询以告诉我数字在列中出现多少次

谁能告诉我为什么这个linq查询不起作用?

请谁能告诉我为什么输出是这样的?(蟒蛇)

我收到运行时错误NZEC请告诉我是什么问题

C ++,Shared_ptr,请告诉我为什么我的代码给出错误?

嗨,我对此有疑问,请告诉我我哪里出错了

pygame跳跃系统出现问题。请告诉我我的代码有什么问题

SQL查询不断告诉我我缺少右括号,但是我没有

谁能告诉我为什么媒体查询是在断点之前注册而不是一个即时定位

谁能告诉我为什么这个查询不起作用?

有人可以告诉我我的Type或linq查询出了什么问题吗

PHP strtok()如果我理解这个权利,请告诉我

请告诉我我的代码有什么问题吗?

Pascal,请告诉我这个循环是如何工作的

有人可以告诉我这种排序算法是什么吗?

为什么我们使用此代码请谁能告诉我

PHP 中的内部连接查询告诉我所有其他的连接查询都这样吗?

查询告诉我客户是否在 3 个查询中

请告诉我这个 UI 名称是如何命名的

请告诉我为什么我的输出中有一个“none”

请告诉我为什么它错了(LCM & GCD)

这是我的连接字符串,请告诉我有什么问题

谁能告诉我排序算法的大 O 时间?

你能告诉我我用来检索客户上次下订单信息的查询有什么问题吗?

请告诉我如何编写nuxt插件'printd'

请告诉我如何制作跟随角色的UI

PHP 请告诉我如何访问对象键