PKU3264-Balanced Lineup

題目：http://poj.org/problem?id=3264
有N(50000)個元素的陣列，給Q(200000)筆詢問[p,q]，回答該區間內最大值-最小值


程式碼：http://codepad.org/BDaEkf3M
經典RMQ(Range Minimum/Maximum Query)問題
資訊科學不少和二分相關、log底數2的事物
想解決這個問題我們可以先看一件事情：
已知[1,4]最小值7、[5,8]最小值3，問[1,8]最小值是多少？(問A)
已知[1,16]最小值3、[3,18]最小值5，問[1,18]最小值是多少？(問B)

於是很簡單發現我們可以預處理一個表格A[50000][15]
其中[15]代表我們取15種不同區間的長度1、2、4、8、…、32768
也就是說A[i][j]意謂「以i開頭，長度len(j)區間的最小值」
可見len(j)=2^j、具體說來對應的區間就是[i, i+len(j)-1]
預處理的這一步就是問A的啟示
兩段恰好相接的區間、可以直接求出合併區間後的最小值
預處理複雜度O(nlgn)

然而現實中我們詢問的區間是任意的，長度不一定恰好是2的冪次
但是從問B發現，假如詢問區間的寬度是18、那麼我們可以找一個最大合適的j值
也就是取從頭算起寬度16的資料、從尾算起寬度16的資料(利用[1,16]和[3,18]來求解[1,18])
具體說來查詢就是[p,q] = min( A[p][j] , A[q-len(j)+1][j] )
每次查詢的複雜度O(1)

最後本題總複雜度O(nlgn + Q)