Всем привет!

На контестах периодически попадаются задачи на запросы на отрезках. Большая часть задач даёт запросы в оффлайне, что даёт большую свободу действий, но всё же часто они сводятся к дереву отрезков, а иногда и алгоритму Мо. Однако иногда в задачах может оказаться так, что оффлайн её решает простой Мо, а в онлайне она становится интересной. В таких ситуациях некоторые люди пытаются поддерживать что-то типа $$$500$$$ разных состояний алгоритма Мо, но я вообще не понимал, о чём они.

Сегодня я сумел придумать версию онлайн Мо, работающую за $$$O(n^{\frac{5}{3}})$$$ в нормальных задачах. Рассмотрим на примере:

Задача о количестве различных чисел на отрезке, запросы онлайн.

Для начала вспомним решение задачи оффлайн с помощью алгоритма Мо. Мы будем поддерживать массив количества вхождений $$$cnt$$$, а также текущее количество различных чисел $$$dif$$$. Тогда движение указателей $$$L$$$ и $$$R$$$ делается тривиально за $$$O(1)$$$, да и алгоритм Мо достаточно известный, так что не будем вдаваться в подробности.