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.