Editorial for Baltic OI '11 P1 - Growing Trees

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.

This problem can be solved by binary searches and a range-update segment tree, but our solution can be faster. If for each subtree in the segment tree, we maintain the biggest value in it. As a result, when we want to find the first element of value $t_i$ ~t_i~, we start the search in the root of the segment tree and we can easily check which subtree the element belongs to. If the biggest element in the left subtree is $t_i$ ~t_i~, then we continue the search in the left subtree. Otherwise, we have to search in the right subtree. This reduces the complexity from $\mathcal O(N + M \log^2 N)$ ~\mathcal O(N + M \log^2 N)~ to $\mathcal O(N + M \log N)$ ~\mathcal O(N + M \log N)~.

Complexity: $\mathcal O(N + M \log N)$ ~\mathcal O(N + M \log N)~

Comments

There are no comments at the moment.