Editorial for DMOPC '18 Contest 4 P4 - Dr. Henri and Lab Data
Submitting an official solution before solving the problem yourself is a bannable offence.
For of points, we can loop over the numbers for each query, and find the appropriate difference in .
For of points, we have two possible solutions. The first solution involves maintaining a range tree of sorted vectors, and using binary search to answer each query in , which can be optimized to . The optimization is left as an exercise to the reader.
Another possible solution is to solve the queries using offline processing. We observe that the answer to a query is the sum minus twice the sum of all numbers less than in the range .
We can compute the first part in , with preprocessing, using a prefix sum array. To handle the second sum, we can sort all queries by their values. We can loop through the values , and update a range tree to contain all elements with a value less than or equal to , and then execute all queries where . This results in a time complexity of per update and query.
For the final of points, we observe that we don't have to loop through . Rather, we see that the values of and are irrelevant when processing offline, and only their relative order matters. Thus we can remap and the values of the queries to the numbers , and solve the problem in the same way as the last subtask.