[POJ 3264]

Balanced Lineup

RMQ

题意是,有长度最多50,000的正整数序列,最多200,000次询问,对于每次询问(l, r),需要输出下标[l, r]范围内序列最大值和最小值的差。

最近啃的是郭华阳的《RMQ与LCA问题》,敲了下基于倍增思想的ST算法。O(nlgn)预处理后,可以O(1)回答每次询问。

之前做这题用的是O(qlgn)的线段树: