Submit Status
N个数排成一列,Q个询问,每次询问一段区间内的数的极差是多少。
第一行两个整数N(1≤N≤50000),Q(1≤Q≤200000)。接下来一行N个整数a1 a2 a3 ....an,(1≤ai≤1000000000)。接下来Q行,每行两个整数L,R(1≤L≤R≤N)。
对于每个询问输出一行,一个整数表示区间内的极差。
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 }