

Revision History 

You have to normalize the array first, as described in the article. After that, you may use the algorithm described at the end of the article. [LATER EDIT] Note that you don't actually normalize A, this is a forced expresion. You just use LCA queries for computing the RMQ queries on the original vector. For that LCA queries you use RMQ queries on a +1 vector, and that's the vector you process. So, the way that's described in the article, it's necesarry to build the cartesian tree first, and compute the euler tour on it in order to have an <O(n), O(1)> RMQ algorithm. However, don't expect to code this algorithm in a topcoder contest;). It's just too long to code:)


You have to normalize the array first, as described in the article. After that, you may use the algorithm described at the end of the article. [LATER EDIT] Note that you don't actually normalize A, this is a forced expresion. You just use LCA queries for computing the RMQ queries on the original vector. For that LCA queries you use RMQ queries on a +1 vector, and that's the vector you process. So, the way that's described in the article, it's necesarry to build the cartesian tree first, and compute the euler tour on it in order to have an <O(n), O(1)> RMQ algorithm. However, don't expect to code this algorithm in a topcoder contest;). It's just takes too long to code:)


You have to normalize the array first, as described in the article. After that, you may use the algorithm described at the end of the article.

