Editorial for DMOPC '14 Contest 2 P6 - Selective Cutting
Submitting an official solution before solving the problem yourself is a bannable offence.
There are many ways to solve this problem. We will describe one such method here. We will sort the queries in descending order of ~q~. We will add trees to a data structure in order of descending height. After we add the last tree of a height ~h~, we can answer all queries with ~q \ge h~ by simply summing from position ~l~ to position ~r~ (we assume that all shorter trees are nonexistent, or have mass 0). This can be done quickly with either a Binary Indexed Tree or Segment Tree. Make sure to output the queries in the correct order after.
Time complexity: ~\mathcal O((N+Q)\log N)~