17
правок
Изменения
Нет описания правки
* <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>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>
Так как в данной задаче порядок чисел на отрезке не важен, важно лишь количество вхождений каждого, то реализация отдельных функций для добавления слева и справа нам не потребуется.
Для простоты будем считать, что все числа '''не превышают <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>. Реализовать его можно, например, используя [[Красно-черное_дерево | Краснокрасно-черное дерево]] Тогда операции будут иметь следующий вид:
'''function''' add('''int''' index):
'''int''' value = arr[index]
'''if''' (cnt[value] != > 0):
current.erase((cnt[value], value))
cnt[a[index]] += 1
current.erase((cnt[value], value))
cnt[a[index]] -= 1
'''if''' (cnt[value] != > 0):
current.insert((cnt[value], value))
