Изменения

В каждый момент времени поддерживаем структуру данных, в которой хранится будем хранить непрерывный отрезок <tex>[a \ldots b]</tex> исходного массива (будем называть его рабочим отрезком), вместе со структурой данных,которая поддерживает умеет обрабатывать следующие операции:* <tex>\mathtt{addLeft(a-1)}</tex>, <tex>\mathtt{addRight(b+1)}</tex> {{---}} операции, которые позволяют добавить элемент в рабочий отрезок слева и справа соответственно.;* <tex>\mathtt{delLeft(a)}</tex>, <tex>\mathtt{delRight(b)}</tex> {{---}} операции, которые позволяют удалить элемент рабочего отрезка слева и справа соответственно.;

Запишем все запросы в массив, некоторым образом отсортируем их отсортируем и определённым способом (который будет описан ниже) будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].

Допустим, что текущий рабочий отрезок — <tex>[a \ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда сначала расширим наш рассмотрим случаи: * Если изначально было <tex> a > l_i </tex>, то будем добавлять в рабочий отрезокэлементы слева по одному, пока граница не совпадёт;используя только операции * Если же это не так, то есть <tex>\mathtt{addLeft}a < l_i </tex>это значит, что в рабочем отрезке присутствуют те элементы, которых там быть не должно, и они должны быть удалены;* При равенстве <tex>a=l_i</tex> никаких действий с левой границей рабочего отрезка производить не потребуется. Аналогично поступим с <tex>b</tex> и <tex>\mathtt{addRight}r_i</tex> . Для компактности и наглядности кода мы сначала расширим рабочий отрезок до отрезка <tex>[l \ldots r]</tex>,где <tex>l = \min(a, l_i)</tex>, а <tex>r = \max(b, r_i)</tex>, а затем удалим лишние элементы при помощи операций <tex>\mathtt{delLeft}</tex>, <tex>\mathtt{delRight}</tex>, чтобы получить отрезок <tex>[l_i \ldots r_i]</tex>, после чего вызовем <tex>\mathtt{answer}</tex> и запомним ответ для этого запроса.

те запросы, для которых <tex>K + 1 \leqslant l_i \leqslant 2 \cdot K</tex> {{---}} во вторую, <tex>2 \cdot K + 1 \leqslant l_i \leqslant 3 \cdot K</tex> {{---}} в третью, и так далее. Будем рассматривать все группы запросов независимо друг от друга. Если внутри каждой группы отсортировать запросы по увеличению правой границеграницы, то асимптотика по времени для обработки одной группы будет нетрудно заметить<tex>O(N + Q_i \cdot K)</tex>, где <tex>Q_i</tex> {{---}} количество запросов, принадлежащих группе под номером <tex>i</tex>. ==Доказательство==Докажем, что для всей на обработку одной группы суммарно будет выполнено уйдёт не больше чем <tex>3 \cdot N + Q_i \cdot K</tex> операций <tex>\mathtt{add}</tex> и <tex>\mathtt{del}</tex> где <tex>Q_i</tex> {{---}} количество запросов, принадлежащих группе под номером <tex>i</tex>.

Для доказательства этого рассмотрим отдельно количество сделанных операций каждого из четырёх типов:* Изначальноизначально, до обработки группы, рабочий отрезок был <tex>[a \ldots b]</tex>, для обработки первого запроса может потребоваться <tex>2 \cdot N</tex> операций <tex>\mathtt{add}</tex>, <tex>\mathtt{del}</tex>;* <tex>\mathtt{delRight}</tex> между отрезками одной группы не произойдёт ни разу, т.к. так как рабочий отрезок внутри одной группы будет только расширяться в сторону правого конца;* <tex>\mathtt{addRight}</tex> в этой группе произойдёт суммарно не больше чем <tex>N</tex> раз, так как минимальная правая граница {{---}} <tex>1</tex>, а максимальная {{---}} <tex>N</tex>;* Для для оставшихся двух операций рассмотрим два последовательных запроса <tex>[l_i \ldots r_i]</tex>, <tex>[l_j \ldots r_j]</tex>. Нетрудно заметить, что так как отрезки принадлежат одной группе, то <tex>|l_i - l_j| < K</tex>, следовательно, количество операций <tex>\mathtt{addLeft}</tex> или <tex>\mathtt{delLeft}</tex> также не будет превосходить <tex>K</tex>, а суммарно для всей группы {{---}} <tex>Q_i \cdot K</tex>.

Таким образом, нетрудно видеть, все группы будут обработаны за время <tex>O\left(\dfrac{N^2}{K} + K \cdot Q\right)</tex>.

При выборе <tex>K = \sqrt{N}</tex> с учётом сортировки по правой границе получается асимптотика времени <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt N)</tex>.

result[q[i].id] = answer() <font color=green>// получаем ответ на [a;...b] </font>

Для простоты будем считать, что все числа '''не превышают <tex>N</tex>''', тогда будем хранить массив <tex>cnt[N + 1]</tex>, где <tex>cnt[value]</tex> - количество вхождений числа <tex>value</tex> в рабочем отрезке. Будем помимо этого массива хранить отсортированное множество <tex>current</tex>, в котором будут содержаться все пары вида <tex>\langle \mathtt{cnt[value]}, \mathtt{value } \rangle</tex>, для ненулевых <tex>cnt[value]</tex>. Реализовать его можно, например, используя [[Красно-черное_дерево | Краснокрасно-черное дерево]] Тогда операции будут иметь следующий вид:

'''if''' (cnt[value] != > 0):

'''if''' (cnt[value] != > 0):

Итоговая асимптотика решения: <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt{N} \cdot \log N)</tex>.

[[Категория:Дискретная_математика,_алгоритмы_и_структуры_данных#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D0.BD.D0.B0.D0.B8.D0.BC.D0.B5.D0.BD.D1.8C.D1.88.D0.B5.D0.BC_.D0.BE.D0.B1.D1.89.D0.B5.D0.BC_.D0.BF.D1.80.D0.B5.D0.B4.D0.BA.D0.B5Задача о наименьшем общем предке]]