Editorial for Mock CCC '22 1 S4 - Berkeley Math Tournament Statistics
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
Comments