In the last Educational Round, I implemented next solution for G problem([problem:2043-G]), and never seen before, solution like this, for online MO problems.↵
↵
[submission:298356157]↵
↵
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.
↵
[submission:298356157]↵
↵
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.
