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


  • 1
    Snoogy  commented on Feb. 23, 2021, 5: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.