http://poj.org/problem?id=3264
题意:输入n个数,有m个询问,每个询问输入l,r,求区间[ l , r ]之间最大数与最小数之差。
思路:
我用的线段树过的,节点增加两个域,分别记录该区间的最大值和最小值。然后设置全局变量maxh和minh动态维护区间[ l, r]中的最大值和最小值。
不过线段树过时间不是一般的慢,3s+。。。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 50005; struct line { int l; int r; int minh; int maxh; }tree[maxn<<2]; int a[maxn]; int maxh; int minh; void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; if(l == r) { tree[v].maxh = a[l]; tree[v].minh = a[l]; return; } int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); tree[v].maxh = max(tree[v*2].maxh,tree[v*2+1].maxh); tree[v].minh = min(tree[v*2].minh,tree[v*2+1].minh); } void query(int v, int l, int r) { if(tree[v].l == l && tree[v].r == r) { maxh = max(maxh,tree[v].maxh); //maxh,minh动态维护 minh = min(minh,tree[v].minh); return; } int mid = (tree[v].l+tree[v].r)>>1; if(r <= mid) query(v*2,l,r); else { if(l > mid) query(v*2+1,l,r); else { query(v*2,l,mid); query(v*2+1,mid+1,r); } } } int main() { int n,m; scanf("%d %d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); build(1,1,n); int l,r; while(m--) { scanf("%d %d",&l,&r); maxh = 0; minh = INF; //不要忘记初始化 query(1,l,r); printf("%d\n",maxh-minh); } return 0; }