RMQ
定义：
A[0...n-1] 目标数组 Log2[1...n] 以2为底i的对数
算法目的：
给定海量询问区间，求解区间最值。
算法核心思想：
(只对最小值进行讨论，最大值的话可以通过原数组求相反数再求最小值获得)
算法分两步：1、预处理 2、询问
1) 预处理
f[i][j] 表示 [i, i + 2j - 1]这个区间内的最小值所在数的下标。
a) 当j = 0，显然f[i][0] = i;
b) 当 j > 0, 由于这个区间长度必定是2的倍数，所以它一定能够拆成两个长度一样的子区间，即[i, i + 2j-1 - 1]和[i + 2j-1, i + 2j - 1]，仔细观察可以发现：
f[i][j-1] 表示的区间是 [i, i + 2j-1 - 1]
f[i + 2j-1][j-1] 表示的区间是 [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) 询问
询问的时候可以把原区间[l, r]拆成两个长度为2k的区间(区间之间允许有交集)，分别用f[l][k] 和 f[r-2k+1][k]表示两个区间内最小值所在的下标。并且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为整数，所以k为log2(r-l+1)的下取整，由于1 <= r-l+1 <= n。
令x = f[l][k], y = f[r-2k+1][k]，询问结果为：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模板只用于求最小值，若要求最大值只需要将原数组取相反数，然后结果再取相反数即可
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]这个区间的最小值 对应数的下标
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的对数 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的区间
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为整数，所以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，求解区间最大最小值的差。
PKU 3368 Frequent values
题意：给定一个长度为N(N <= 100000)的单调不降序列Si，然后是Q(Q <= 100000)条询问，问给定区间出现最多的数的次数。
题解：离散化 + RMQ
由于Q很大，询问的复杂度必须要log(n)，这样一来就先确定下来是线段树了，这个题目有个限制条件，所有数都是单调不增的排列的，换言之，就是说如果两个数相同的话，他们之间的所有数必定也和它们相同。于是就有了O(Q log(n))(用RMQ就是O(Q)了)的算法：
对于所有的数均设定一个组号，也可以叫离散化吧，相同的数有相同的组号，然后将各个数的频率统计后记录在一个数组中，表示该类数的大小，对于输入的询问[x, y]，直接查询它们在哪个组，分三种情况讨论：
1) 如果x和y在一个组，那么最长长度就是y - x + 1
2) 如果组号相差1，那么找出两者的分界点z(假设z点和x点组号相同)，那么答案就是Max{z - x + 1, y - z}
3) 如果相差大于1，那么先将两头截掉，统计大的记录，再和中间那段的最大值比较大小，中间那段的最大值可以用线段树 或者 RMQ区间查询最值。
本题还有线段树的解法，代码见：
http://www.cppblog.com/menjitianya/archive/2011/03/29/142966.html
PKU 2452 Sticks Problem
题意：给定一个长度为N(N <= 50000)的数列Si，要求找到Si和Sj(1 <= i < j <= N)使得所有的Sk(i < k < j)大于Si并且小于Sj。如果能找到这样的对数，输出最大的j-i，否则输出-1。
题解：二分 + RMQ(或线段树)
首先考虑最暴力的情况，自然是枚举i和j，然后判i+1到j-1这些数是否满足条件，如果满足则更新j-i，这样的复杂度是O(n3)的，时间上显然说不过去。然后试着降掉一维，同样枚举i和j，然后在判断是否满足条件时，利用RMQ求区间最值，这样的复杂度就降到了O(n2logn)，然而N的数据量还是不允许我们这么做，于是只能试着寻找O(n logn)的算法。那么我们尝试枚举一个j，看看能不能通过它来确定i，这里有一条很明显的性质，就是如果Si到Sj-1都小于Sj那么Si+1到Sj-1必然也都小于Sj，这条性质可以让我们二分枚举i的左边界t，采用二分找到最小的t使得St-1 >= Sj，也即St < Sj(t <= i < j)，找的过程可以采用RMQ求出区间最大值进行比较，然后问题就转化成了在以下数列：St St+1 ... Sj-1 Sj 中找到最小的i(t <= i < j)使得Si+1到Sj都大于Si，很明显，又是一个区间最值的问题，利用RMQ求出[t, j-1]最小值的下标，就是我们要求的i，如果有多个，必须选择最靠近j的，这是显然的。这样总的复杂度就降到O(n(logn)2)，
当然，求最值的时候可以采用线段树代替RMQ。
线段树的代码见：
http://www.cppblog.com/menjitianya/archive/2011/03/29/142962.html
ZJU 2859 Matrix Searching
题意：给定一个n*n(n <= 300)的矩阵，然后是(T <= 106)次询问，每次询问某个子矩阵中的最小值。
题解：二维RMQ(或 二维线段树)
裸模板题。思想和一维RMQ一样，二维情况的f数组是四维的。
线段树的代码见：
http://www.cppblog.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
逻辑强题。首先记录下每个信息所在的连续块，如果两个信息的连续块相同，说明它们之间的年份全部连续。年份的查找可以采用二分查找，然后就是分情况讨论了，对输入的两个年份Y和X，利用二分查找找到最大的小于等于给定年份的那条记录fY和fX。
一.如果两者查到的记录都在输入数据中出现过，然后判断他们是不是属于一个连续的块，只需要下标索引即可，然后是两种情况：
1. 如果属于同一个连续块，说明中间的年份全部出现过，然后利用线段树查找fY的年份的最大降水量Yr，[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果满足以下条件：(Yr >= Xr && Zr < Xr)则说明条件属实，是true的情况，否则则是false。
2.如果不属于同一个连续块，说明中间的年份不是全部出现过，然后利用RMQ查找fY的年份的最大降水量Yr，[fY+1, fX-1]的最大降水量Zr和fX的最大降水量Xr，如果满足以下条件：(Yr >= Xr && Zr < Xr)则说明当前条件属实，但是也有可能没出现过的记录破坏这个条件，所以是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的年份在先前的数据中都没有出现过，这肯定是maybe的情况。
PKU 2201 Cartesian Tree
题意：给定N(N <= 50000)个整数对(key,
a)，要求将他们组织成一棵树二叉树，并且对于树的任意一个结点，满足如下两个性质：
1) 当前结点的a值大于它父节点的a值(小顶堆的性质)；
2) 当前结点的key值大于左子树的key值，并且小于右子树的key值(排序二叉树的性质)；
题目保证所有的key值和a值都不同。
题解：首先将所有整数对按key值递增排序，这样我们只需要对数组进行切分，如果第t个结点作为根结点，那么[1, t-1]必定是它的左子树集合，[t+1,
N]必定是它的右子树集合，这样就能够保证第二个条件，而第一个条件需要满足父节点的a值小于左右子树的a值，所以第t个结点必定是所有数中a值最小的，于是可以规约出一个递归算法，对于当前区间[l, r]，找到区间内a值最小的作为根结点，然后将它左边的区间和右边的区间进行相同的递归运算。初始区间为[1, N]，当[l,
r]满足 l > r即为递归出口。求区间最小值可以采用RMQ。
总的时间复杂度为排序的时间复杂度O(N log N)。