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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define _DEBUG
#ifndef _DEBUG
#define fin stdin
#define fout stdout
#endif
inline int fmin(int a, int b) {
return a < b ? a : b;
}
inline int fmax(int a, int b) {
return a > b ? a : b;
}
class SegTree {
private:
struct Node {
int l, r;
int max;
int min;
};
Node tree[200001];
void Build(int left, int right, int p);
public:
SegTree(int left, int right);
void Insert(int what, int where, int p);
void Query(int left, int right, int *min, int *max, int p);
};
SegTree::SegTree(int left, int right) {
memset(tree, 0, sizeof(tree));
Build(left, right, 1);
}
void SegTree::Build(int left, int right, int p) {
tree[p].l = left;
tree[p].r = right;
tree[p].max = 0;
tree[p].min = 0x7FFFFFFF;
if(left < right) {
Build(left, (left + right) / 2, p * 2);
Build((left + right) / 2 + 1, right, p * 2 + 1);
}
}
void SegTree::Insert(int what, int where, int p) {
tree[p].max = fmax(tree[p].max, what);
tree[p].min = fmin(tree[p].min, what);
if(tree[p].l != tree[p].r) {
if(where <= (tree[p].l + tree[p].r) / 2) {
Insert(what, where, p * 2);
}else{
Insert(what, where, p * 2 + 1);
}
}
}
void SegTree::Query(int left, int right, int *min, int *max, int p = 1) {
if(left <= tree[p].l && tree[p].r <= right) {
*min = tree[p].min;
*max = tree[p].max;
return;
}
int leftmin = 0x7FFFFFFF, leftmax = 0, rightmin = 0x7FFFFFFF, rightmax = 0;
if(left <= (tree[p].l + tree[p].r) / 2) {
Query(left, right, &leftmin, &leftmax, p * 2);
}
if(right > (tree[p].l + tree[p].r) / 2) {
Query(left, right, &rightmin, &rightmax, p * 2 + 1);
}
*min = fmin(leftmin, rightmin);
*max = fmax(leftmax, rightmax);
}
int main() {
#ifdef _DEBUG
FILE *fin = fopen("3264.in", "r");
FILE *fout = fopen("3264.out", "w");
#endif
int n, q;
int cow;
fscanf(fin, "%d %d", &n, &q);
SegTree Tree(1, n);
for(int i = 0; i < n; i++) {
fscanf(fin, "%d", &cow);
Tree.Insert(cow, i+1, 1);
}
for(int i = 0; i < q; i++) {
int a, b;
fscanf(fin, "%d %d", &a, &b);
int min = 0x7FFFFFFF;
int max = 0;
Tree.Query(a, b, &min, &max);
fprintf(fout, "%d\n", max - min);
}
return 0;
}
|