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.
Update: the solution has been hacked, and I have added a new way to optimize code, if we have a MO segment that needed less than 3000 iterations to reach the range from the query, then we can just pick that MO segment. In another case, if we have less than 500 created MO segments, we create a new segment. If we have create 500 MO segments already and no one don't reached by 3000 iterations, just pick a segment with less iterations(like in the first solution).
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.
