Подскажите пожалуйста эффективный алгоритм Range Mex Query

Question

Подскажите пожалуйста эффективный алгоритм 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]) для всех (l[i], r[i]),

Функция 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) медленно. Пожалуйста, расскажите мне более быстрый алгоритм.

7

algorithm c++game-theory

Решение

Другие решения

Давайте обработаем наши запросы и наши элементы слева направо, что-то вроде

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] у которого есть 1 если суффикс начинается с позиции i содержит номер j а также 0 иначе. Учтите также, что мы рассчитали суммы префиксов для каждого contains[i] по отдельности. В этом случае мы могли бы ответить на каждый конкретный запрос суффикса в O(log N) время с помощью бинарного поиска: мы должны просто найти первый ноль в соответствующем contains[l[i]] массив, который является точно первой позицией, где частичная сумма равна индексу, а не индексу +1. К сожалению, такие массивы могут занять O(N^2) пространство и необходимость O(N^2) время для каждого обновления.

Итак, мы должны оптимизировать. Давайте построим 2-мерный ареал дерева с операциями диапазона «запрос суммы» и «назначение». В таком дереве мы можем запросить сумму по любому под прямоугольнику и присвоить одно и то же значение всем элементам любого под прямоугольника в O(log^2 N) время, которое позволяет нам сделать обновление в O(log^2 N) время и запросы в O(log^3 N) время, давая время сложность O(Nlog^2 N + Qlog^3 N), Пространство сложности O((N + Q)log^2 N) (и то же время для инициализации массивов) достигается с помощью отложенной инициализации.

UP: Давайте пересмотрим, как работает запрос в деревьях диапазонов с помощью «суммы». Для одномерного дерева (чтобы этот ответ не был слишком длинным), это примерно так:

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Итак, один из звонков детям всегда возвращает тривиальный ответ (0 или уже вычислено sum). Итак, вместо того, чтобы делать O(log N) запросы к двумерному дереву в алгоритме двоичного поиска, мы могли бы реализовать специальную процедуру для поиска, очень похожую на эту get запрос. Сначала следует получить значение левого потомка (который занимает O(1) так как он уже рассчитан), проверьте, находится ли искомый узел слева (эта сумма меньше числа листов в левом поддереве), и перейдите влево или вправо на основе этой информации. Этот подход будет дополнительно оптимизировать запрос O(log^2 N) время (так как сейчас это одна древовидная операция), давая в результате сложность O((N + Q)log^2 N)) и время и пространство.

Не уверен, что это решение достаточно быстро для обоих Q а также N вплоть до 10^5, но это, вероятно, может быть дополнительно оптимизировано.

1

Источник

Accepted Answer

Вот O((Q + N) log N) решение:

Давайте переберем все позиции в массиве слева направо и сохраним последние вхождения для каждого значения в дереве сегментов (дерево сегментов должно хранить минимум в каждом узле).
После добавления i-го числа мы можем ответить на все запросы с правой границей, равной i,
Ответ наименьшее значение 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)

Функция поиска меньшего размера выглядит следующим образом:

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 функция, показанная выше, и я уверен, что это достаточно быстро для данных ограничений.

4