An easy problem A
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
N个数排成一列，Q个询问，每次询问一段区间内的数的极差是多少。
Input
第一行两个整数N(1≤N≤50000),Q(1≤Q≤200000)。接下来一行N个整数a1 a2 a3 ....an,(1≤ai≤1000000000)。接下来Q行，每行两个整数L,R(1≤L≤R≤N)。
Output
对于每个询问输出一行，一个整数表示区间内的极差。
Sample input and output
| Sample Input | Sample Output |
|---|---|
5 3 3 2 7 9 10 1 5 2 3 3 5 |
8 5 3 |
题目链接：http://acm.uestc.edu.cn/#/contest/show/155
分析：线段树点更新裸题，继续复习线段树，这题要算的是极差，只需要建树和查询两部分，无需更新，所以建树的时候只要去求最大值和最小值即可，然后极差一减得出答案！
下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=200020; 4 struct Node 5 { 6 int l,r,minn,maxn; 7 }tree[N<<2]; 8 void build(int l,int r,int pos) 9 { 10 tree[pos].l=l; 11 tree[pos].r=r; 12 if(l==r) 13 { 14 scanf("%d",&tree[pos].maxn); 15 tree[pos].minn=tree[pos].maxn; 16 return; 17 } 18 int mid=(l+r)/2; 19 build(l,mid,pos*2); 20 build(mid+1,r,pos*2+1); 21 tree[pos].maxn=max(tree[pos*2].maxn,tree[pos*2+1].maxn); 22 tree[pos].minn=min(tree[pos*2].minn,tree[pos*2+1].minn); 23 } 24 int query1(int l,int r,int pos) 25 { 26 if(tree[pos].l==l&&tree[pos].r==r) 27 return tree[pos].minn; 28 int mid=(tree[pos].l+tree[pos].r)/2; 29 if(r<=mid) 30 return query1(l,r,pos*2); 31 else if(l>mid) 32 return query1(l,r,pos*2+1); 33 else return min(query1(l,mid,pos*2),query1(mid+1,r,pos*2+1)); 34 } 35 int query2(int l,int r,int pos) 36 { 37 if(tree[pos].l==l&&tree[pos].r==r) 38 return tree[pos].maxn; 39 int mid=(tree[pos].l+tree[pos].r)/2; 40 if(r<=mid) 41 return query2(l,r,pos*2); 42 else if(l>mid) 43 return query2(l,r,pos*2+1); 44 else return max(query2(l,mid,pos*2),query2(mid+1,r,pos*2+1)); 45 } 46 int main() 47 { 48 int x,y; 49 scanf("%d%d",&x,&y); 50 build(1,x,1); 51 while(y--) 52 { 53 int p,q; 54 scanf("%d%d",&p,&q); 55 printf("%d\n",query2(p,q,1)-query1(p,q,1)); 56 } 57 return 0; 58 }
