Editorial for Baltic OI '11 P1 - Growing Trees - Olympiads Online Judge

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)$ $O (N + M \log^{2} N)$ to $\mathcal O(N + M \log N)$ $O (N + M \log N)$ .

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

Comments

There are no comments at the moment.