题意就是让你求区间最大和最小值的差值。
这题可以用线段树，也可以用Tarjan 的Sparse Table算法（参考刘汝佳训练指南197），这里我用了ST算法，还有要说明的是题目描述的数据范围是不准确的如果你数组开比50000大一点点的话是会RE的。
代码：
//poj 3263 RMQ //2013-07-30-21.39 #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn = 100005; int dmax[maxn][30]; int dmin[maxn][30]; int a[maxn]; void init(int n) { for (int i = 1; i <= n; i++) { dmax[i][0] = a[i]; dmin[i][0] = a[i]; } for (int j = 1; (1<<j) <= n; j++) { for (int i = 1; i + j - 1 <= n; i++) { dmax[i][j] = max(dmax[i][j-1], dmax[i+(1<<(j-1))][j-1]); dmin[i][j] = min(dmin[i][j-1], dmin[i+(1<<(j-1))][j-1]); } } } int RMQ(int l, int r) { int k = 0; while ((1<<(k+1)) <= r-l+1) k++; return (max(dmax[l][k], dmax[r-(1<<k)+1][k]) - min(dmin[l][k], dmin[r-(1<<k)+1][k])); } int main() { int n, q; int l, r; while (scanf("%d %d", &n, &q) != EOF) { for (int i = 1; i <= n; i++) scanf("%d", &a[i]); init(n); while (q--) { scanf("%d %d", &l, &r); printf("%d\n", RMQ(l, r)); } } return 0; }
