Editorial for DMOPC '14 Contest 2 P6 - Selective Cutting - Olympiads Online Judge

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 \geq 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)$ $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.