Как решить автономный Range-Mex запрос с обновлениями?

Question

ВНИМАНИЕ! Я прочитал все те же вопросы в стеке и на некоторых других сайтах.Все они неверны или работают больше, чем TL.

Теперь о задаче:

Размер входного массива: N <= 5*10^5 and 0 <= array[i] <= N

(Размер массива меньшеили равно 5 * 10 ^ 5, каждый элемент меньше или равен размеру массива)

Запросы: Q <= 2,5*10^5

Мы должны ответить на запрос (l r) как MEX-функция в диапазоне [l, r] входного массива или выполнение запроса (p x) как array[p] = x

Надеюсь, вы можете помочь мне с некоторыми идеями)

Answer 1

• Разделите массив на блоки размером n ^2/3 .Это оставит нас с n ^1/3 блоков.
• Для каждой пары xy блоков, x 2/3 ... y * n ^2/3 ], а затем составьте набор с отсутствующими номерами.Существует n ^2/3 таких пар, отсчет которых равен O (n), поэтому набор равен O (n log n) => O (n ^5/3 * log n)
• Для обновления мы обновим все пары блоков, в которых позиция находится в диапазоне.Обновление состоит в уменьшении 1 от счетчика текущего значения, если счетчик становится равным 0, добавьте значение к набору, а затем добавьте 1 к счетчику нового значения и удалите это значение из набора.Это O (log n) для каждой пары блоков, что дает нам стоимость O (n ^2/3 * log n) для каждого обновления.
• Для запроса найдите самую большую пару блоков, которая полностью заключена в границы запроса.Затем посмотрите на значения массива, отсутствующие в этих границах как справа, так и слева, и отсортируйте их.С этим + набором пропущенных значений мы можем вычислить мекс для диапазона.Обратите внимание, что мы должны проверить влево и вправо не более 2n ^2/3 значений, поэтому сортировка будет стоить O (2n ^2/3 * log 2n ^{2 /3} ).Это стоимость каждого запроса.

В целом сложность составляет O (n ^5/3 * log n + u * n ^2/3 * log n + q * 2n ^2/3 * log 2n ^2/3 ), где q - количество запросов диапазона, а u - количество обновлений.

Немного оптимизаций:

• Для обновления вы можете использовать отложенное обновление и просто сообщить диапазонам, что нам нужно сделать это обновление, но обновлять только пару блоков, когда онотребуется по запросу.