Editorial for Monkey Motel
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Let be the calculated price of each treehouse
.
Notice that has a bound of
. The maximum
can be constructed when each node is labeled with a distinct ID from
to
. In this case
will be
.
To find efficiently, store a set for each treehouse which will consist of prices of all treehouses in its subtree. To merge the set of a treehouse and all its children, we can use Small-To-Large Merging.
Next, notice that if a treehouse has a price of
, its parent treehouse
will always have a price
such that
. Therefore to calculate
for a treehouse
, we loop from
(for all children treehouses
) to
and check for the first positive integer not in the set of all prices.
Denote to be the answer for some price
by only considering treehouses with
.
Since a query refers to treehouses with prices greater than or equal to , we denote
to be the answer considering treehouses with price
.
can be calculated in the following manner:
This is similar to running a suffix minimum by looping from to
. Note that ties should be broken by the treehouse with minimal ID, as mentioned in the problem statement. From here, we can answer queries for a certain
by outputting
.
Time Complexity:
Comments