## Editorial for DMOPC '18 Contest 4 P4 - Dr. Henri and Lab Data

**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.**

Authors:

For of points, we can loop over the numbers for each query, and find the appropriate difference in .

**Time Complexity:**

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.

**Time Complexity:**

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.

**Time Complexity:**

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.

**Time Complexity:**

## Comments