# An easy problem A

##### Time Limit: 2000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

N个数排成一列，Q个询问，每次询问一段区间内的数的极差是多少。

## Sample input and output

Sample Input

Sample Output

5 3 3 2 7 9 10 1 5 2 3 3 5

8 5 3

``` 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 }```

0 条评论

## 相关文章

33210

6006

### POJ 2001 Shortest Prefixes

Description A prefix of a string is a substring starting at the beginning of th...

2869

### POJ-2329 Nearest number - 2（BFS）

Nearest number - 2 Time Limit: 5000MS Memory Limit: 65536K Total Submis...

2474

### ZOJ 3537 Cake(凸包判定+区间DP)

Cake Time Limit: 1 Second Memory Limit: 32768 KB You want to hold a par...

3789

### HOJ 2985 Wavio Sequence（最长递增子序列以及其O(n*logn)算法）

Wavio Sequence My Tags (Edit) Source : UVA Time limit : 1 sec Memor...

2816

### 《Kotlin极简教程》第五章 Kotlin面向对象编程（OOP）一个OOP版本的HelloWorld构造函数传参Data Class定义接口&实现之写pojo bean定一个Rectangle对象封

We frequently create a class to do nothing but hold data. In such a class some s...

2344

### PAT 甲级 1104 sum of Number Segments

1104. Sum of Number Segments (20) 时间限制 200 ms 内存限制 65536 kB 代码长度限制 16...

2835

1181

### CodeForces 666B World Tour(spfa+枚举)

B. World Tour time limit per test 5 seconds memory limit per test 512 mega...

3384