RMQ:（区间最值问题）
本质上是动态规划，用d(i, j) 表示 从 i 开始的长度为 2^j 的一段元素的最小值，，则可以用递推的方法计算d(i, j) ： d(i, j) = min{ d(i, j-1), d(i + 2^(j-1), j-1)}
由于2^j <= n 因此 d数组中元素个数不超过nlogn, 因此总时间复杂度为O（nlogn）;
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <set>#include <map>#include <queue>#include <cmath>#include <stack>#define LL long longusing namespace std;const int MAXN = 50000 + 10;int d[MAXN][20];int A[MAXN];int n, q;void RMQ_init_min(){for(int i=0;i<n;i++) d[i][0] = A[i];for(int j=1;(1<<j) <= n;j++)for(int i=0;i+(1<<j)-1 < n;i++)d[i][j] = min(d[i][j-1], d[i+(1<<(j-1))][j-1]);}int RMQ_min(int L, int R){int k = 0;while((1<<(k+1)) <= R – L + 1) k++;return min(d[L][k], d[R-(1<<k)+1][k]);}int dp[MAXN][20];void RMQ_init_max(){for(int i=0;i<n;i++) dp[i][0] = A[i];for(int j=1;(1<<j) <= n;j++)for(int i=0;i+(1<<j)-1 < n;i++)dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);}int RMQ_max(int L, int R){int k = 0;while((1<<(k+1)) <= R – L + 1) k++;return max(dp[L][k], dp[R-(1<<k)+1][k]);}int main(){while(scanf("%d%d", &n, &q)!=EOF){for(int i=0;i<n;i++)scanf("%d", &A[i]);RMQ_init_min();RMQ_init_max();int L, R;while(q–){scanf("%d%d", &L, &R);int l = RMQ_min(L-1, R-1);int r = RMQ_max(L-1, R-1);printf("%d\n", r – l);}}return 0;}
这一生我只牵你的手，因为今生有你早已足够。
