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

Question

У меня есть вопрос об этой проблеме.

Вопрос

• Вам дают последовательность 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 - минимальное исключенное значение.
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; 
} 

Скажите, пожалуйста, как решить.

EDIT: O (N^2) работает медленно. Скажите, пожалуйста, более быстрый алгоритм.

Answer 1

Вот 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) 

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

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

Answer 2

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

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-мерный range tree с операциями диапазона «запрос суммы» и «присвоения». В таком дереве мы можем запросить сумму на любом суб-прямоугольнике и присваивать одно и то же значение всем элементам любого суб-прямоугольника в 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: Давайте рассмотрим, как работает запрос в деревьях диапазона с «суммой».Для 1-мерного дерева (не сделать этот ответ слишком долго), это что-то вроде этого:

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, но, возможно, оно будет еще более оптимизировано.