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


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.

Authors: Kirito

For 10\% of points, we can loop over the numbers A_l, A_{l+1}, \ldots, A_{r-1} A_r for each query, and find the appropriate difference in \mathcal O(N).

Time Complexity: \mathcal O(NQ)

For 60\% 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 \mathcal O(\log^2 N), which can be optimized to \mathcal O(\log N). The optimization is left as an exercise to the reader.

Time Complexity: \mathcal O((N + Q)\log N)

Another possible solution is to solve the queries using offline processing. We observe that the answer to a query q = {l, r, k} is the sum A_l + A_{l + 1} + A_{l+2} + \cdots + A_{r-2} + A_{r-1} + A_r minus twice the sum of all numbers less than k in the range A[l,r].

We can compute the first part in \mathcal O(1), with \mathcal O(N) preprocessing, using a prefix sum array. To handle the second sum, we can sort all queries by their k values. We can loop through the values i = 0, 1, 2, 3, \ldots, \max(A), and update a range tree to contain all elements with a value less than or equal to i, and then execute all queries where i = k - 1. This results in a time complexity of \mathcal O(\log N) per update and query.

Time Complexity: \mathcal O((N + Q)\log N)

For the final 30\% of points, we observe that we don't have to loop through i = 0, 1, 2, 3, \ldots, \max(A). Rather, we see that the values of A and k are irrelevant when processing offline, and only their relative order matters. Thus we can remap A[1], A[2], A[3], \ldots A[N] and the k values of the queries to the numbers 1, 2, 3, \ldots, N + Q, and solve the problem in the same way as the last subtask.

Time Complexity: \mathcal O((N + Q)\log N)


Comments

There are no comments at the moment.