Editorial for Mock CCC '22 1 S4 - Berkeley Math Tournament Statistics
Submitting an official solution before solving the problem yourself is a bannable offence.
The intended solution for 1 mark is direct simulation.
There are no intended solutions for the intermediate subtasks, we simply wanted to reward folks for constant optimizing or removing log factors in their solutions.
The intended solution has complexity . Use Mo's algorithm and bucket queries by left endpoint. Maintain a frequency count that persistently tracks all frequencies for indices to the right of the bucket, and then for each query adjust the frequency count by indices present in that bucket.