RMQ
定義：
A[0...n-1] 目標數(shù)組 Log2[1...n] 以2為底i的對數(shù)
算法目的：
給定海量詢問區(qū)間，求解區(qū)間最值。
算法核心思想：
(只對最小值進行討論，最大值的話可以通過原數(shù)組求相反數(shù)再求最小值獲得)
算法分兩步：1、預處理 2、詢問
1) 預處理
f[i][j] 表示 [i, i + 2j - 1]這個區(qū)間內(nèi)的最小值所在數(shù)的下標。
a) 當j = 0，顯然f[i][0] = i;
b) 當 j > 0, 由于這個區(qū)間長度必定是2的倍數(shù)，所以它一定能夠拆成兩個長度一樣的子區(qū)間，即[i, i + 2j-1 - 1]和[i + 2j-1, i + 2j - 1]，仔細觀察可以發(fā)現(xiàn)：
f[i][j-1] 表示的區(qū)間是 [i, i + 2j-1 - 1]
f[i + 2j-1][j-1] 表示的區(qū)間是 [i, i + 2j-1 - 1]
為了方便閱讀，令x = f[i][j-1], y = f[i + 2j-1][j-1]，所以f[i][j] = A[x] < A[y] ? x : y;
2) 詢問
詢問的時候可以把原區(qū)間[l, r]拆成兩個長度為2k的區(qū)間(區(qū)間之間允許有交集)，分別用f[l][k] 和 f[r-2k+1][k]表示兩個區(qū)間內(nèi)最小值所在的下標。并且k的取值要求能夠使得 [l, l+2k-1] 和 [r-2k+1,r] 的并集 為 [l, r]。
于是 k為滿足l+2k-1 <= r并且值最大，即2k <= r-l+1，則k <= log2(r-l+1), 又k為整數(shù)，所以k為log2(r-l+1)的下取整，由于1 <= r-l+1 <= n。
令x = f[l][k], y = f[r-2k+1][k]，詢問結(jié)果為：A[x] < A[y] ? x : y;
算法復雜度：
預處理：O( n log(n) )
詢問：O(1)
給出我的模板：
1 #define MAXN 50010
2 #define MAXL 16
3 #define MAXQ 200100
4
5
6 // 該RMQ模板只用于求最小值，若要求最大值只需要將原數(shù)組取相反數(shù)，然后結(jié)果再取相反數(shù)即可
7
8 class RMQData {
9 public:
10 int index;
11 int val;
12 }rd[MAXN];
13
14 int n;
15 int Log2[MAXN]; // Log2[i] = log2(i)
16 int f[MAXN][MAXL]; // f[i][j] 表示 [i, (i + 2^j) - 1]這個區(qū)間的最小值 對應數(shù)的下標
17 // f[i][j] = min{ f[i][j-1] , f[ i + 2^(j-1) ][j-1] }
18
19 void RMQ_Init() {
20 int i, j, p;
21
22 // 計算log以2為底的i的對數(shù) log2(i)
23 Log2[1] = 0;
24 for(i = 2; i < n; i++) {
25 Log2[i] = Log2[i-1];
26 if( 1<<(Log2[i] + 1) == i ) {
27 Log2[i] ++;
28 }
29 }
30 for(j = 0; j < MAXL; j++) {
31 for(i = 0; i < n; i++) {
32 if(j == 0) {
33 f[i][0] = i;
34 }else {
35 f[i][j] = f[i][j-1];
36 p = i + (1<<(j-1));
37 if(p < n) {
38 if( rd[ f[p][j-1] ].val < rd[ f[i][j] ].val ) {
39 f[i][j] = f[p][j-1];
40 }
41 }
42 }
43 }
44 }
45 }
46
47 // 詢問的時候拆成兩個長度為2^k的區(qū)間
48 // f[l][k] 和 f[r-2^k+1][k]
49 // 并且k的取值要求能夠使得 [l,l+2^k-1] 和 [r-2^k+1,r] 的并集 為 [l, r]
50 // 于是 k為滿足l+2^k-1 <= r并且值最大，即2^k <= r-l+1
51 // k <= log2(r-l+1), 又k為整數(shù)，所以k為log2(r-l+1)的下取整
52 int RMQ_Query(int l, int r) {
53 if(l > r) {
54 int tmp = l;
55 l = r;
56 r = tmp;
57 }
58 int k = Log2[r - l + 1];
59 return rd[ f[l][k] ].val < rd[ f[r-(1<<k)+1][k] ].val ? f[l][k] : f[r-(1<<k)+1][k];
60 }
PKU 3264 Balanced Lineup
裸RMQ，求解區(qū)間最大最小值的差。
PKU 3368 Frequent values
題意：給定一個長度為N(N <= 100000)的單調(diào)不降序列Si，然后是Q(Q <= 100000)條詢問，問給定區(qū)間出現(xiàn)最多的數(shù)的次數(shù)。
題解：離散化 + RMQ
由于Q很大，詢問的復雜度必須要log(n)，這樣一來就先確定下來是線段樹了，這個題目有個限制條件，所有數(shù)都是單調(diào)不增的排列的，換言之，就是說如果兩個數(shù)相同的話，他們之間的所有數(shù)必定也和它們相同。于是就有了O(Q log(n))(用RMQ就是O(Q)了)的算法：
對于所有的數(shù)均設定一個組號，也可以叫離散化吧，相同的數(shù)有相同的組號，然后將各個數(shù)的頻率統(tǒng)計后記錄在一個數(shù)組中，表示該類數(shù)的大小，對于輸入的詢問[x, y]，直接查詢它們在哪個組，分三種情況討論：
1) 如果x和y在一個組，那么最長長度就是y - x + 1
2) 如果組號相差1，那么找出兩者的分界點z(假設z點和x點組號相同)，那么答案就是Max{z - x + 1, y - z}
3) 如果相差大于1，那么先將兩頭截掉，統(tǒng)計大的記錄，再和中間那段的最大值比較大小，中間那段的最大值可以用線段樹 或者 RMQ區(qū)間查詢最值。
本題還有線段樹的解法，代碼見：
http://www.shnenglu.com/menjitianya/archive/2011/03/29/142966.html
PKU 2452 Sticks Problem
題意：給定一個長度為N(N <= 50000)的數(shù)列Si，要求找到Si和Sj(1 <= i < j <= N)使得所有的Sk(i < k < j)大于Si并且小于Sj。如果能找到這樣的對數(shù)，輸出最大的j-i，否則輸出-1。
題解：二分 + RMQ(或線段樹)
首先考慮最暴力的情況，自然是枚舉i和j，然后判i+1到j-1這些數(shù)是否滿足條件，如果滿足則更新j-i，這樣的復雜度是O(n3)的，時間上顯然說不過去。然后試著降掉一維，同樣枚舉i和j，然后在判斷是否滿足條件時，利用RMQ求區(qū)間最值，這樣的復雜度就降到了O(n2logn)，然而N的數(shù)據(jù)量還是不允許我們這么做，于是只能試著尋找O(n logn)的算法。那么我們嘗試枚舉一個j，看看能不能通過它來確定i，這里有一條很明顯的性質(zhì)，就是如果Si到Sj-1都小于Sj那么Si+1到Sj-1必然也都小于Sj，這條性質(zhì)可以讓我們二分枚舉i的左邊界t，采用二分找到最小的t使得St-1 >= Sj，也即St < Sj(t <= i < j)，找的過程可以采用RMQ求出區(qū)間最大值進行比較，然后問題就轉(zhuǎn)化成了在以下數(shù)列：St St+1 ... Sj-1 Sj 中找到最小的i(t <= i < j)使得Si+1到Sj都大于Si，很明顯，又是一個區(qū)間最值的問題，利用RMQ求出[t, j-1]最小值的下標，就是我們要求的i，如果有多個，必須選擇最靠近j的，這是顯然的。這樣總的復雜度就降到O(n(logn)2)，
當然，求最值的時候可以采用線段樹代替RMQ。
線段樹的代碼見：
http://www.shnenglu.com/menjitianya/archive/2011/03/29/142962.html
ZJU 2859 Matrix Searching
題意：給定一個n*n(n <= 300)的矩陣，然后是(T <= 106)次詢問，每次詢問某個子矩陣中的最小值。
題解：二維RMQ(或 二維線段樹)
裸模板題。思想和一維RMQ一樣，二維情況的f數(shù)組是四維的。
線段樹的代碼見：
http://www.shnenglu.com/menjitianya/archive/2011/03/30/143010.html
PKU 2637 WorstWeather Ever
題意：給定N(N <= 50000)條信息，表示第yi年的降水量是ri，然后給出M(M <= 10000)條詢問，每條詢問的格式是Y X，表示自從第Y年以來X這一年是最大的降水量，問這句話正確與否。
正確的判斷條件是：
1.Y到X這些年的所有年份的降水量已知。
2.Y的降水量 >= X的降水量。
3.對于每個Z，Y < Z < X，Z的降水量小于X的降水量。
可能正確的判斷條件是：
其中有一年的降水量不知道。
錯誤的判斷條件是：
其他情況。
題解：二分 + RMQ
邏輯強題。首先記錄下每個信息所在的連續(xù)塊，如果兩個信息的連續(xù)塊相同，說明它們之間的年份全部連續(xù)。年份的查找可以采用二分查找，然后就是分情況討論了，對輸入的兩個年份Y和X，利用二分查找找到最大的小于等于給定年份的那條記錄fY和fX。
一.如果兩者查到的記錄都在輸入數(shù)據(jù)中出現(xiàn)過，然后判斷他們是不是屬于一個連續(xù)的塊，只需要下標索引即可，然后是兩種情況：
1. 如果屬于同一個連續(xù)塊，說明中間的年份全部出現(xiàn)過，然后利用線段樹查找fY的年份的最大降水量Yr，[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果滿足以下條件：(Yr >= Xr && Zr < Xr)則說明條件屬實，是true的情況，否則則是false。
2.如果不屬于同一個連續(xù)塊，說明中間的年份不是全部出現(xiàn)過，然后利用RMQ查找fY的年份的最大降水量Yr，[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果滿足以下條件：(Yr >= Xr && Zr < Xr)則說明當前條件屬實，但是也有可能沒出現(xiàn)過的記錄破壞這個條件，所以是maybe的情況，否則則是false。
二.如果X能夠查到，則利用線段樹查找[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果滿足以下條件：Zr < Xr則說明條件有可能屬實，是maybe的情況，否則則是false。
三.如果Y能查到，這個條件就比較隱秘了，因為需要滿足(Yr >= Xr && Zr < Xr)，而Zr和Xr無從得知，但是我們可以知道Yr >= Xr > Zr，于是只要判斷當前的Zr是否小于Yr。
如果成立，則是maybe，否則就是false。
四.最后一種情況就是X和Y的年份在先前的數(shù)據(jù)中都沒有出現(xiàn)過，這肯定是maybe的情況。
PKU 2201 Cartesian Tree
題意：給定N(N <= 50000)個整數(shù)對(key,
a)，要求將他們組織成一棵樹二叉樹，并且對于樹的任意一個結(jié)點，滿足如下兩個性質(zhì)：
1) 當前結(jié)點的a值大于它父節(jié)點的a值(小頂堆的性質(zhì))；
2) 當前結(jié)點的key值大于左子樹的key值，并且小于右子樹的key值(排序二叉樹的性質(zhì))；
題目保證所有的key值和a值都不同。
題解：首先將所有整數(shù)對按key值遞增排序，這樣我們只需要對數(shù)組進行切分，如果第t個結(jié)點作為根結(jié)點，那么[1, t-1]必定是它的左子樹集合，[t+1,
N]必定是它的右子樹集合，這樣就能夠保證第二個條件，而第一個條件需要滿足父節(jié)點的a值小于左右子樹的a值，所以第t個結(jié)點必定是所有數(shù)中a值最小的，于是可以規(guī)約出一個遞歸算法，對于當前區(qū)間[l, r]，找到區(qū)間內(nèi)a值最小的作為根結(jié)點，然后將它左邊的區(qū)間和右邊的區(qū)間進行相同的遞歸運算。初始區(qū)間為[1, N]，當[l,
r]滿足 l > r即為遞歸出口。求區(qū)間最小值可以采用RMQ。
總的時間復雜度為排序的時間復雜度O(N log N)。