一段区间的最值问题，用线段树或RMQ皆可。两种代码都贴上：又是空间换时间。。
RMQ 解法：（8168KB 1625ms）
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> using namespace std; #define N 50003 int a[N],dmin[N][20],dmax[N][20],n; void RMQ_init() { int i,j; for(i=1;i<=n;i++) dmin[i][0] = dmax[i][0] = a[i]; for(j=1;(1<<j)<=n;j++) { for(i=1;i+(1<<j)-1<=n;i++) { dmin[i][j] = min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]); dmax[i][j] = max(dmax[i][j-1],dmax[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 q,i; while(scanf("%d%d",&n,&q)!=EOF) { for(i=1;i<=n;i++) scanf("%d",&a[i]); RMQ_init(); while(q--) { int l,r; scanf("%d%d",&l,&r); if(l>r) swap(l,r); printf("%d ",RMQ(l,r)); } } return 0; }
线段树解法：（1172KB 2297ms）
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> using namespace std; #define N 50003 struct node { int maxi,mini; }tree[4*N]; void pushup(int rt) { tree[rt].maxi = max(tree[2*rt].maxi,tree[2*rt+1].maxi); tree[rt].mini = min(tree[2*rt].mini,tree[2*rt+1].mini); } void build(int l,int r,int rt) { if(l == r) { scanf("%d",&tree[rt].maxi); tree[rt].mini = tree[rt].maxi; return; } int mid = (l+r)/2; build(l,mid,2*rt); build(mid+1,r,2*rt+1); pushup(rt); } int query_max(int l,int r,int aa,int bb,int rt) { if(aa>r || bb<l) return -100000; if(aa<=l && bb>=r) return tree[rt].maxi; int mid = (l+r)/2; return max(query_max(l,mid,aa,bb,2*rt),query_max(mid+1,r,aa,bb,2*rt+1)); } int query_min(int l,int r,int aa,int bb,int rt) { if(aa>r || bb<l) return 100000000; if(aa<=l && bb>=r) return tree[rt].mini; int mid = (l+r)/2; return min(query_min(l,mid,aa,bb,2*rt),query_min(mid+1,r,aa,bb,2*rt+1)); } int main() { int n,q,i; while(scanf("%d%d",&n,&q)!=EOF) { build(1,n,1); for(i=1;i<=q;i++) { int l,r; scanf("%d%d",&l,&r); if(l>r) swap(l,r); printf("%d ",query_max(1,n,l,r,1)-query_min(1,n,l,r,1)); } } return 0; }