Hello everyone! In contests, problems involving range queries appear periodically. Most problems provide queries offline, which allows for greater flexibility in solving them, but often they reduce to using a segment tree or Mo's algorithm. However, sometimes a problem that is easily solvable offline with Mo's algorithm becomes interesting in the online version. In such cases, some people try to maintain something like $$$500$$$ different states of Mo's algorithm—I never really understood what was meant by that.

Today, I managed to come up with an online version of Mo's algorithm that works in $$$O(n^{\frac{5}{3}})$$$ time and memory for standard problems. For asymptotic analysis, I'll assume $$$n = q$$$. I'm not the first to come up with this idea. As it turns out, here there was a discussion where this idea was proposed, but as in the previous blog, I want to explain it in more detail so that more people know about it.

In this blog, I want to break down how to solve a problem from a recent Educational Round using online Mo's algorithm.

2043G - Problem with Queries This problem has too much going on—update queries and even encoded inputs. Let's first try solving the offline version without update queries. I should clarify that instead of counting the number of indices $$$i \lt j$$$ where $$$a_i \neq a_j$$$, I'll count the opposite—the number of pairs where $$$a_i = a_j$$$. From this value, it's easy to derive the answer to the original problem, but counting pairs with equal values is slightly simpler to maintain.

The problem itself is a simple exercise on Mo's algorithm.