題目鏈接：http://poj.org/PRoblem?id=3264
題意： 有一個長度為 n 的序列，然后有 q 個提問，對于每一個提問，輸入兩個數 L, R，輸出這n個序列中L到R的最大值與最小值的差。
題解： 看上去就是一道線段樹的題目，這兩天剛接觸線段樹，于是寫了一發。題目本身并不難，主要就是需要注意一下細節，其他的基本上就沒有什么問題了。 推薦線段樹好文章：http://blog.csdn.net/metalseed/article/details/8039326
代碼：
#include <cstdio>#include <algorithm>using namespace std;const int size = 200005;struct _seg { int l, r; int mx, mn;} seg[size];int n, q, peop[size];void build(int x, int y, int num) { seg[num].l = x; seg[num].r = y; if(x == y) { seg[num].mx = peop[x]; seg[num].mn = peop[y]; } else { build(x, (x+y)/2, num*2); build((x+y)/2+1, y, num*2+1); seg[num].mn = min(seg[num*2].mn, seg[num*2+1].mn); seg[num].mx = max(seg[num*2].mx, seg[num*2+1].mx); }}const int inf = 1 << 26;int resMn = inf, resMx = -inf;void query(int x, int y, int num) { if(x <= seg[num].l && y >= seg[num].r) { resMn = min(resMn, seg[num].mn); resMx = max(resMx, seg[num].mx); return ; } int mid = (seg[num].l+seg[num].r) >> 1; if(y <= mid) query(x, y, num*2); else if(x > mid) query(x, y, num*2+1); else { query(x, y, num*2); query(x, y, num*2+1); }}int main() { // freopen("POJ3264.in", "r", stdin); scanf("%d %d", &n, &q); for ( int i = 1; i <= n; i ++ ) scanf("%d", &peop[i]); build(1, n, 1); for ( int i = 1; i <= q; i ++ ) { int x, y; resMn = inf; resMx = -inf; scanf("%d %d", &x, &y); query(x, y, 1); int ans = resMx-resMn; printf("%d/n", ans); } return 0;}新聞熱點
疑難解答
