Range Minimum(Maximum) Query, RMQ

從這位強者的網誌轉錄:
http://gozule.blogspot.com/2009/02/range-minimummaximum-query-rmq.html

Input：array A[0, N]
Output： the index of minimum(maximum) value between two given indices.
RMQ的功能是若有一群資料放在array中，在經過preprocessing後，可在O(1)的時間內找出index i~j之間的最小(大)的元素。目前preprocessing最快是O(n)，也就是只需要O(n)的時間就可以處理完成。

以下介紹O(nlog(n))的preprocessing方法，O(n)的方法是由此法去改進，所以先了解此法相當重要且因程式碼容易撰寫，所以也相當適合在ACM中使用。

假設array的長度2的n次方。
建立一個大小為n x log(n)的矩陣M，用來存放RMQ的結果，其中M[i][j]是指以index i開頭，長度為2^j次方內最小元素的index。
使用dynamic programming方法建立M，需O(nlogn) time。

//time complexity: O(nlogn)
void preprocess(int M[MAXN][LOGMAXN], int A[MAXN], int N)
{
int i, j;

//initialize M for the intervals with length 1
for (i = 0; i < N; i++)
M[i][0] = i;
//compute values from smaller to bigger intervals
for (j = 1; 1 << j <= N; j++)
for (i = 0; i + (1 << j) - 1 < N; i++)
if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
M[i][j] = M[i][j - 1];
else
M[i][j] = M[i + (1 << (j - 1))][j - 1];
}

//output: the index of the minimum value between index i and j
int RMQ(int i, int j, int M[MAXN][LOGMAXN], int A[MAXN], int N)
{
if(i<0 || i>=N || j<0 || j>=N)
return -1;

if(i > j) //swap i, j
i ^= j, j ^= i, i ^= j;

int k = (int)(log(j-i)/log(2.0)),
rem = j-(1< return (A[M[i][k]] > A[M[rem][k]] ? M[rem][k] : M[i][k]);
}

宜蘭縣三星鄉的漿腥淫

他這個人阿，簡直太可愛了，又很真實

不用擔心他把話往肚子裡藏，只需要擔心他把你耳膜撐爆就好

整天劈哩啪啦停不下來，就是愛他這點，她是我女友，沒錯



無敵high，不是很容易高潮的意思，是他很愛笑

也很愛逗身邊的人一起笑，或是逗身邊的人哭，自己笑

還笑很爽

不愛洗內褲，內褲明明七八十件，還是會全部躺在洗衣籃裡面，髒髒的

不穿內褲上學

還喜歡穿睡衣出門，我蠻愛的，因為這點跟我一樣

他很喜歡狗，但我不喜歡他摸完狗摸我，我有潔癖

總之

我愛她一杯子