http://d.hatena.ne.jp/Ozy/20070516#p1 の続き 最速は Range Minimum Query and Lowest Common Ancestor http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor とここからリンクされている資料を参考に数パターン作ってみました…

予想通りRMQではなかった。

なかなか良さげな問題 http://acm.pku.edu.cn/JudgeOnline/problem?id=2823 巨大な配列(最大10^6)の中で長さkの区間内の最大値と最小値を求める問題。 配列のサイズn=10、区間の長さk=3とすれば、 Window position Minimum value Maximum value [1 3 -1] -3 …