JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Re: Good job. Revision History (2 edits)
 Re: Good job. (response to post by hungson175) 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 RMQ algorithm.However, don't expect to code this algorithm in a topcoder contest;). It's just too long to code:)
 Re: Good job. (response to post by hungson175) 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 RMQ algorithm.However, don't expect to code this algorithm in a topcoder contest;). It's just takes too long to code:)
 Re: Good job. (response to post by hungson175) 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.