Всем привет!
На контестах периодически попадаются задачи на запросы на отрезках. Большая часть задач даёт запросы в оффлайне, что даёт большую свободу действий, но всё же часто они сводятся к дереву отрезков, а иногда и алгоритму Мо. Однако иногда в задачах может оказаться так, что оффлайн её решает простой Мо, а в онлайне она становится интересной. В таких ситуациях некоторые люди пытаются поддерживать что-то типа $$$500$$$ разных состояний алгоритма Мо, но я вообще не понимал, о чём они.
Сегодня я сумел придумать версию онлайн Мо, работающую за $$$O(n^{\frac{5}{3}})$$$ времени и памяти в нормальных задачах. Для анализа асимптотики я буду считать, что $$$n = q$$$.
2043G - Problem with Queries
Для начала вспомним решение задачи оффлайн с помощью алгоритма Мо. Мы будем поддерживать массив количества вхождений $$$cnt$$$, а также текущее количество различных чисел $$$dif$$$. Тогда движение указателей $$$L$$$ и $$$R$$$ делается тривиально за $$$O(1)$$$, да и алгоритм Мо достаточно известный, так что не будем вдаваться в подробности реализации.
Однако вспомним анализ асимптотики с геометрической стороны. Размер блока для алгоритма Мо обозначим за $$$B \approx \sqrt{n}$$$.
К сожалению в онлайн версии мы не можем выбирать порядок обхода квадратиков, да и в каждый квадратик нам может понадобиться заходить несколько раз, поэтому нужен другой подход. Понятно, что лишь одной парой указателей нам не обойтись, поскольку в таком случае на каждый запрос мы будем отвечать за $$$O(n)$$$, что долго. Назовём \textit{состоянием} всю необходимую информацию, которую мы обычно поддерживаем для одного отрезка. Я хочу создать несколько \textit{состояний}, чтобы от какого-то из них можно было быстро дойти до нашего запроса.
Выберем $$$B \approx n^{\frac{2}{3}}$$$. Теперь у нас мало квадратиков, всего $$$\frac{n^2}{B^2} = n^{\frac{2}{3}}$$$. Мы не будем делать никакого предподсчёта, сразу будем отвечать на запросы.
Ответ на запрос происходит так:
Определим квадратик, в котором находится запрос. Если
