Привет, Codeforces!
Мне довольно сильно нравятся всякие корневые, поэтому я начал думать в их сторону и придумал 3д-мо в онлайне(почти).
Задача: дан массив из N чисел, Q запросов(в онлайне) к этому массиву и число K. Каждый запрос принадлежит одному из двух видов:
update pos val — присвоить a[pos] значение val; get L R — узнать количество чисел, встречающихся хотя бы K раз на отрезке с L по R.
Решение: (далее / везде будет обозначать деление с округлением вниз)
Назовем ящиком следующую структуру: индексы L R(начало и конец текущего полуинтервала, в 0-индексации), массив подсчета(если он нужен) и ответ(res). Пусть C - кубический корень из N.
Теперь заведем C^2 ящиков и зададим им следующие границы: у ящика i(в 0-индексации) L = (i / C) * (N / C), R = (i % C) * (N / C). Если R <= L, то просто игнорируем данный ящик. Заведем массив подсчета cnt для этого массива и насчитаем ответ(в данной задаче границы двигаются за O(1), ведь надо уметь добавлять число в множество и удалять из него, а это cnt[X] += 1 и cnt[X] -= 1 и res += 1 и res -= 1, если cnt[X] перешло через K).
Как отвечать на запросы? Для первого типа переберем все ящики и для тех, у которых выполняется L <= pos < R обновим ответ. Запрос выполнен за O(C^2). Для второго типа возьмем отрезок с индексом i = (L / (N / C)) * C + (R / (N / C)) и сдвинем границы.
Пусть L* — левая координата ящика. Тогда L* = (((L / (N / C)) * C + R / (N / C)) / C) * (N / C). R / (N / C) <= C, тогда L* = (((L / (N / C) + B) * C) / C) * (N / C), B = 0 или B = 1, L* = L + B * (N / C). Тогда расстояние от L* до L не превосходит B * (N / C), а значит не превосходит N / C = C^2, аналогично для R, значит мы найдем ответ за O(C^2). Итоговая асимптотика: O((N + Q) * C^2) времени и O(N * C^2) памяти. Возьмем теперь любое С. Итоговая асимптотика: O((N + Q) * max(N / C, C * 2)) времени и O(N * C^2) памяти. Иногда может быть полезно брать разные C, так как при уменьшении C уменьшается затрачиваемая память. Данный алгоритм решает и другие задачи, где в оффлайне работает 3д-мо. Единственная проблема состоит в сжатии координат. Без него время работы домножается на константу map или какой-нибудь хеш таблицы. Но, например, в задачах про mex нас не интересуют числа, большие n, а в задачах про различные числа можно сжимать в онлайне, ведь важно только разным присваивать разные значения.
