题目链接:
思路分析：
典型的区间统计问题,要求求出某段区间中的极值，可以使用线段树求解。
在线段树结点中存储区间中的最小值与最大值；查询时使用线段树的查询
方法并稍加修改即可进行查询区间中最大与最小值的功能。
代码(线段树解法)：
#include#include #include using namespace std;const int MAX_N = 200000;const int N_VAL = 50000 + 10;struct SegTreeNode{ int valMin, valMax;};SegTreeNode segTree[MAX_N];int val[N_VAL];int valMax, valMin;int Max(int a, int b) { return a > b ? a : b; }int Min(int a, int b) { return a > b ? b : a; }void Build(int root, int nbegin, int nend, int arr[]){ if (nbegin == nend) { segTree[root].valMax = arr[nbegin]; segTree[root].valMin = arr[nbegin]; } else { int mid = (nbegin + nend) / 2; Build(2 * root, nbegin, mid, arr); Build(2 * root + 1, mid + 1, nend, arr); segTree[root].valMax = Max(segTree[2 * root].valMax, segTree[2 * root + 1].valMax); segTree[root].valMin = Min(segTree[2 * root].valMin, segTree[2 * root + 1].valMin); }}void Query(int root, int nbegin, int nend, int qbegin, int qend){ if (nbegin > qend || nend < qbegin) return; if (qbegin <= nbegin && qend >= nend) { if (valMax < segTree[root].valMax) valMax = segTree[root].valMax; if (valMin > segTree[root].valMin) valMin = segTree[root].valMin; return; } int mid = (nbegin + nend) / 2; Query(2 * root, nbegin, mid, qbegin, qend); Query(2 * root + 1, mid + 1, nend, qbegin, qend);}int main(){ int qbegin, qend; int count = 0, N, Q; scanf("%d%d", &N, &Q); while (count++ < N) scanf("%d", &val[count]); Build(1, 1, N, val); while (Q--) { valMax = INT_MIN, valMin = INT_MAX; scanf("%d%d", &qbegin, &qend); Query(1, 1, N, qbegin, qend); printf("%d\n", valMax - valMin); } return 0;}
代码(RMQ解法)：
#include#include #include using namespace std;const int MAX_L = 16;const int MAX_N = 200000 + 10;int height[MAX_N];int max_h[MAX_N][MAX_L], min_h[MAX_N][MAX_L];void RmqMaxInit(int n){ for (int j = 0; j < MAX_L; ++j) { for (int i = 0; i < n; ++i) { if (j == 0) max_h[i][j] = height[i]; else { max_h[i][j] = max_h[i][j - 1]; int p = i + (1 << (j - 1)); if (p < n) { if (max_h[p][j - 1] > max_h[i][j]) max_h[i][j] = max_h[p][j - 1]; } } } }}int RmqMaxQuery(int l, int r){ if (l > r) { int temp = l; l = r; r = temp; } int k = log(r - l + 1) / log(2); return max_h[l][k] > max_h[r - (1 << k) + 1][k] ? max_h[l][k] : max_h[r - (1 << k) + 1][k];}void RmqMinInit(int n){ for (int j = 0; j < MAX_L; ++j) { for (int i = 0; i < n; ++i) { if (j == 0) min_h[i][j] = height[i]; else { min_h[i][j] = min_h[i][j - 1]; int p = i + (1 << (j - 1)); if (p < n) { if (min_h[p][j - 1] < min_h[i][j]) min_h[i][j] = min_h[p][j - 1]; } } } }}int RmqMinQuery(int l, int r){ if (l > r) { int temp = l; l = r; r = temp; } int k = log(r - l + 1) / log(2); return min_h[l][k] < min_h[r - (1 << k) + 1][k] ? min_h[l][k] : min_h[r - (1 << k) + 1][k];}int main(){ int num_len, query_num; scanf("%d %d", &num_len, &query_num); for (int i = 0; i < num_len; ++i) scanf("%d", &height[i]); RmqMaxInit(num_len); RmqMinInit(num_len); for (int i = 0; i < query_num; ++i) { int l = 0, r = 0; int min_height = 0, max_height = 0; scanf("%d %d", &l, &r); max_height = RmqMaxQuery(l - 1, r - 1); min_height = RmqMinQuery(l - 1, r - 1); printf("%d\n", max_height - min_height); } return 0;}