RMQ
定義：
A[0...n-1] 目標(biāo)數(shù)組 Log2[1...n] 以2為底i的對(duì)數(shù)
算法目的：
給定海量詢問(wèn)區(qū)間，求解區(qū)間最值。
算法核心思想：
(只對(duì)最小值進(jìn)行討論，最大值的話可以通過(guò)原數(shù)組求相反數(shù)再求最小值獲得)
算法分兩步：1、預(yù)處理 2、詢問(wèn)
1) 預(yù)處理
f[i][j] 表示 [i, i + 2j - 1]這個(gè)區(qū)間內(nèi)的最小值所在數(shù)的下標(biāo)。
a) 當(dāng)j = 0，顯然f[i][0] = i;
b) 當(dāng) j > 0, 由于這個(gè)區(qū)間長(zhǎng)度必定是2的倍數(shù)，所以它一定能夠拆成兩個(gè)長(zhǎng)度一樣的子區(qū)間，即[i, i + 2j-1 - 1]和[i + 2j-1, i + 2j - 1]，仔細(xì)觀察可以發(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) 詢問(wèn)
詢問(wèn)的時(shí)候可以把原區(qū)間[l, r]拆成兩個(gè)長(zhǎng)度為2k的區(qū)間(區(qū)間之間允許有交集)，分別用f[l][k] 和 f[r-2k+1][k]表示兩個(gè)區(qū)間內(nèi)最小值所在的下標(biāo)。并且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]，詢問(wèn)結(jié)果為：A[x] < A[y] ? x : y;
算法復(fù)雜度：
預(yù)處理：O( n log(n) )
詢問(wè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]這個(gè)區(qū)間的最小值 對(duì)應(yīng)數(shù)的下標(biāo)
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 // 計(jì)算log以2為底的i的對(duì)數(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 // 詢問(wèn)的時(shí)候拆成兩個(gè)長(zhǎng)度為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
題意：給定一個(gè)長(zhǎng)度為N(N <= 100000)的單調(diào)不降序列Si，然后是Q(Q <= 100000)條詢問(wèn)，問(wèn)給定區(qū)間出現(xiàn)最多的數(shù)的次數(shù)。
題解：離散化 + RMQ
由于Q很大，詢問(wèn)的復(fù)雜度必須要log(n)，這樣一來(lái)就先確定下來(lái)是線段樹(shù)了，這個(gè)題目有個(gè)限制條件，所有數(shù)都是單調(diào)不增的排列的，換言之，就是說(shuō)如果兩個(gè)數(shù)相同的話，他們之間的所有數(shù)必定也和它們相同。于是就有了O(Q log(n))(用RMQ就是O(Q)了)的算法：
對(duì)于所有的數(shù)均設(shè)定一個(gè)組號(hào)，也可以叫離散化吧，相同的數(shù)有相同的組號(hào)，然后將各個(gè)數(shù)的頻率統(tǒng)計(jì)后記錄在一個(gè)數(shù)組中，表示該類(lèi)數(shù)的大小，對(duì)于輸入的詢問(wèn)[x, y]，直接查詢它們?cè)谀膫€(gè)組，分三種情況討論：
1) 如果x和y在一個(gè)組，那么最長(zhǎng)長(zhǎng)度就是y - x + 1
2) 如果組號(hào)相差1，那么找出兩者的分界點(diǎn)z(假設(shè)z點(diǎn)和x點(diǎn)組號(hào)相同)，那么答案就是Max{z - x + 1, y - z}
3) 如果相差大于1，那么先將兩頭截掉，統(tǒng)計(jì)大的記錄，再和中間那段的最大值比較大小，中間那段的最大值可以用線段樹(shù) 或者 RMQ區(qū)間查詢最值。
本題還有線段樹(shù)的解法，代碼見(jiàn)：
http://www.shnenglu.com/menjitianya/archive/2011/03/29/142966.html
PKU 2452 Sticks Problem
題意：給定一個(gè)長(zhǎng)度為N(N <= 50000)的數(shù)列Si，要求找到Si和Sj(1 <= i < j <= N)使得所有的Sk(i < k < j)大于Si并且小于Sj。如果能找到這樣的對(duì)數(shù)，輸出最大的j-i，否則輸出-1。
題解：二分 + RMQ(或線段樹(shù))
首先考慮最暴力的情況，自然是枚舉i和j，然后判i+1到j-1這些數(shù)是否滿足條件，如果滿足則更新j-i，這樣的復(fù)雜度是O(n3)的，時(shí)間上顯然說(shuō)不過(guò)去。然后試著降掉一維，同樣枚舉i和j，然后在判斷是否滿足條件時(shí)，利用RMQ求區(qū)間最值，這樣的復(fù)雜度就降到了O(n2logn)，然而N的數(shù)據(jù)量還是不允許我們這么做，于是只能試著尋找O(n logn)的算法。那么我們嘗試枚舉一個(gè)j，看看能不能通過(guò)它來(lái)確定i，這里有一條很明顯的性質(zhì)，就是如果Si到Sj-1都小于Sj那么Si+1到Sj-1必然也都小于Sj，這條性質(zhì)可以讓我們二分枚舉i的左邊界t，采用二分找到最小的t使得St-1 >= Sj，也即St < Sj(t <= i < j)，找的過(guò)程可以采用RMQ求出區(qū)間最大值進(jìn)行比較，然后問(wèn)題就轉(zhuǎn)化成了在以下數(shù)列：St St+1 ... Sj-1 Sj 中找到最小的i(t <= i < j)使得Si+1到Sj都大于Si，很明顯，又是一個(gè)區(qū)間最值的問(wèn)題，利用RMQ求出[t, j-1]最小值的下標(biāo)，就是我們要求的i，如果有多個(gè)，必須選擇最靠近j的，這是顯然的。這樣總的復(fù)雜度就降到O(n(logn)2)，
當(dāng)然，求最值的時(shí)候可以采用線段樹(shù)代替RMQ。
線段樹(shù)的代碼見(jiàn)：
http://www.shnenglu.com/menjitianya/archive/2011/03/29/142962.html
ZJU 2859 Matrix Searching
題意：給定一個(gè)n*n(n <= 300)的矩陣，然后是(T <= 106)次詢問(wèn)，每次詢問(wèn)某個(gè)子矩陣中的最小值。
題解：二維RMQ(或 二維線段樹(shù))
裸模板題。思想和一維RMQ一樣，二維情況的f數(shù)組是四維的。
線段樹(shù)的代碼見(jiàn)：
http://www.shnenglu.com/menjitianya/archive/2011/03/30/143010.html
PKU 2637 WorstWeather Ever
題意：給定N(N <= 50000)條信息，表示第yi年的降水量是ri，然后給出M(M <= 10000)條詢問(wèn)，每條詢問(wèn)的格式是Y X，表示自從第Y年以來(lái)X這一年是最大的降水量，問(wèn)這句話正確與否。
正確的判斷條件是：
1.Y到X這些年的所有年份的降水量已知。
2.Y的降水量 >= X的降水量。
3.對(duì)于每個(gè)Z，Y < Z < X，Z的降水量小于X的降水量。
可能正確的判斷條件是：
其中有一年的降水量不知道。
錯(cuò)誤的判斷條件是：
其他情況。
題解：二分 + RMQ
邏輯強(qiáng)題。首先記錄下每個(gè)信息所在的連續(xù)塊，如果兩個(gè)信息的連續(xù)塊相同，說(shuō)明它們之間的年份全部連續(xù)。年份的查找可以采用二分查找，然后就是分情況討論了，對(duì)輸入的兩個(gè)年份Y和X，利用二分查找找到最大的小于等于給定年份的那條記錄fY和fX。
一.如果兩者查到的記錄都在輸入數(shù)據(jù)中出現(xiàn)過(guò)，然后判斷他們是不是屬于一個(gè)連續(xù)的塊，只需要下標(biāo)索引即可，然后是兩種情況：
1. 如果屬于同一個(gè)連續(xù)塊，說(shuō)明中間的年份全部出現(xiàn)過(guò)，然后利用線段樹(shù)查找fY的年份的最大降水量Yr，[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果滿足以下條件：(Yr >= Xr && Zr < Xr)則說(shuō)明條件屬實(shí)，是true的情況，否則則是false。
2.如果不屬于同一個(gè)連續(xù)塊，說(shuō)明中間的年份不是全部出現(xiàn)過(guò)，然后利用RMQ查找fY的年份的最大降水量Yr，[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果滿足以下條件：(Yr >= Xr && Zr < Xr)則說(shuō)明當(dāng)前條件屬實(shí)，但是也有可能沒(méi)出現(xiàn)過(guò)的記錄破壞這個(gè)條件，所以是maybe的情況，否則則是false。
二.如果X能夠查到，則利用線段樹(shù)查找[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果滿足以下條件：Zr < Xr則說(shuō)明條件有可能屬實(shí)，是maybe的情況，否則則是false。
三.如果Y能查到，這個(gè)條件就比較隱秘了，因?yàn)樾枰獫M足(Yr >= Xr && Zr < Xr)，而Zr和Xr無(wú)從得知，但是我們可以知道Yr >= Xr > Zr，于是只要判斷當(dāng)前的Zr是否小于Yr。
如果成立，則是maybe，否則就是false。
四.最后一種情況就是X和Y的年份在先前的數(shù)據(jù)中都沒(méi)有出現(xiàn)過(guò)，這肯定是maybe的情況。
PKU 2201 Cartesian Tree
題意：給定N(N <= 50000)個(gè)整數(shù)對(duì)(key,
a)，要求將他們組織成一棵樹(shù)二叉樹(shù)，并且對(duì)于樹(shù)的任意一個(gè)結(jié)點(diǎn)，滿足如下兩個(gè)性質(zhì)：
1) 當(dāng)前結(jié)點(diǎn)的a值大于它父節(jié)點(diǎn)的a值(小頂堆的性質(zhì))；
2) 當(dāng)前結(jié)點(diǎn)的key值大于左子樹(shù)的key值，并且小于右子樹(shù)的key值(排序二叉樹(shù)的性質(zhì))；
題目保證所有的key值和a值都不同。
題解：首先將所有整數(shù)對(duì)按key值遞增排序，這樣我們只需要對(duì)數(shù)組進(jìn)行切分，如果第t個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)，那么[1, t-1]必定是它的左子樹(shù)集合，[t+1,
N]必定是它的右子樹(shù)集合，這樣就能夠保證第二個(gè)條件，而第一個(gè)條件需要滿足父節(jié)點(diǎn)的a值小于左右子樹(shù)的a值，所以第t個(gè)結(jié)點(diǎn)必定是所有數(shù)中a值最小的，于是可以規(guī)約出一個(gè)遞歸算法，對(duì)于當(dāng)前區(qū)間[l, r]，找到區(qū)間內(nèi)a值最小的作為根結(jié)點(diǎn)，然后將它左邊的區(qū)間和右邊的區(qū)間進(jìn)行相同的遞歸運(yùn)算。初始區(qū)間為[1, N]，當(dāng)[l,
r]滿足 l > r即為遞歸出口。求區(qū)間最小值可以采用RMQ。
總的時(shí)間復(fù)雜度為排序的時(shí)間復(fù)雜度O(N log N)。