Привет, 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, а в задачах про различные числа можно сжимать в онлайне, ведь важно только разным присваивать разные значения.

Hello, Codeforces!

I really enjoy working with square roots, so I started thinking in that direction and came up with a 3D Mo's algorithm in an (almost) online format.

Problem: Given an array of N numbers and Q queries (in online mode) to this array, along with a number K. Each query belongs to one of two types: 1. update pos val — assign the value val to a[pos]. 2. get L R — find out how many numbers appear at least K times in the segment from L to R.

Solution: (the symbol / will be used to denote integer division)

Let's define a "bucket" as a structure with the following elements: indices L and R (start and end of the current half-interval, using 0-based indexing), a counting array (if needed), and a result (res). Let C be the cubic root of N. Now, let's create C^2 buckets and set their boundaries as follows: for bucket i (0-based), let L = (i / C) * (N / C) and R = (i % C) * (N / C). If R <= L, simply ignore this bucket. Create a count array cnt for this array and compute the result (in this problem, the boundaries move in O(1) since we need to be able to add a number to the set and remove it, which can be done with cnt[X] += 1, cnt[X] -= 1, and updating res when cnt[X] passes the threshold K).

How to handle queries? For the first type, iterate through all the buckets, and for those that satisfy the condition L <= pos < R, update the result. This query is handled in O(C^2). For the second type, take the segment with the index i = (L / (N / C)) * C + (R / (N / C)) and shift the boundaries. Let L* be the left coordinate of the bucket. Then L* = (((L / (N / C)) * C + R / (N / C)) / C) * (N / C). Since R / (N / C) <= C, we get L* = (((L / (N / C) + B) * C) / C) * (N / C), where B = 0 or B = 1, so L* = L + B * (N / C). Therefore, the distance from L* to L does not exceed B * (N / C), which means it does not exceed N / C = C^2. Similarly, this holds for R, which means we can find the answer in O(C^2). The overall complexity is O((N + Q) * C^2) in time and O(N * C^2) in space.

Now, let's consider any value of C. The final asymptotic complexity is O((N + Q) * max(N / C, C^2)) in time and O(N * C^2) in space. It might be useful to use different values of C, as decreasing C reduces the memory consumption. This algorithm can also be used to solve other problems where Mo's algorithm works in offline mode. The only issue is coordinate compression. Without it, the runtime is multiplied by a constant due to the map or some kind of hash table. However, for example, in problems involving mex, we are not interested in numbers larger than n, and in problems involving distinct numbers, we can perform compression online, as it is only important to assign different values to different numbers.