题目链接：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;}新闻热点
疑难解答
