线段树

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

A - An easy problem A

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

Submit Status

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

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

Sample Output

1
2
3
8
5
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50000;

typedef struct
{
    int left,right,maxv,minv;
}Node;
Node rt[MAXN<<2];
int a[MAXN+5];

void build(int x, int L, int R)
{
    rt[x].left = L; rt[x].right = R;
    if(L==R)
    {
        rt[x].maxv = rt[x].minv = a[L];
        return ;
    }
    int mid = L + R >>1;
    build(x<<1,L,mid); build((x<<1)+1,mid+1,R);
    rt[x].maxv = max(rt[x<<1].maxv,rt[(x<<1)+1].maxv);
    rt[x].minv = min(rt[x<<1].minv,rt[(x<<1)+1].minv);
}

Node query(int x, int L, int R)
{
    Node t,tt;
    int mid = (rt[x].left + rt[x].right)>>1;
    if(L == rt[x].left && R == rt[x].right)
    {
        return rt[x];
    }
    else if(R<=mid)
    {
        tt = query(x<<1,L,R);
        t.maxv = tt.maxv;
        t.minv = tt.minv;
        return t;
    }
    else if(L>mid)
    {
        tt = query((x<<1)+1,L,R);
        t.maxv = tt.maxv;
        t.minv = tt.minv;
        return t;
    }
    else
    {
        t = query(x<<1,L,mid);
        tt = query((x<<1)+1,mid+1,R);
        t.maxv = max(t.maxv,tt.maxv);
        t.minv = min(t.minv,tt.minv);
        return t;
    }

}

int main()
{
    int n,q,l,r;
    Node t;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    build(1,1,n);
    //for(int i=1;i<=9;++i)
        //printf("%d,%d\t",rt[i].maxv,rt[i].minv);
    while(q--)
    {
        scanf("%d %d",&l,&r);
        t = query(1,l,r);
        printf("%d\n",t.maxv-t.minv);
    }

    return 0;
}