Editorial for DMOPC '14 Contest 2 P6 - Selective Cutting

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.

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$ ~q~. We will add trees to a data structure in order of descending height. After we add the last tree of a height $h$ ~h~, we can answer all queries with $q \ge h$ ~q \ge h~ by simply summing from position $l$ ~l~ to position $r$ ~r~ (we assume that all shorter trees are nonexistent, or have mass $0$ ~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)$ ~\mathcal O((N+Q) \log N)~

Comments

1

Snoogy commented on Feb. 23, 2021, 10:43 p.m.

I think there is some confusion with a tree's height. The problem statement refers to trees as having mass, not height.