In the last Educational Round, I implemented next solution for G problem(2043-G - Problem with Queries), and never seen before, solution like this, for online MO problems.
In the problems, we have to find number of pairs of unequal values in the some range. Also, we have updates, and queries — online.
Firstly, I change our task to find pairs of equal values, and imediatelly think about MO(offline solution of problem). Instead of one supported MO segment, I decided to support 500 MO segments. In the updates, I just update MO segments that have that value inside of segment. And for the second type of queries, firstly I find MO segment that needed less iterations to reach the range from the query.
I am curious whether it should pass the tests and about its complexity. Also, have you seen this technique before? Personally, I did not encounter any blogs about this.
