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
102
103
104
105
106
107
108
109
110
111
112
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = b; i >= a; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(5e4)+10;
ll N,T,H[MAXN],trx[MAXN],trd[MAXN];
inline ll lowbit(ll x){
return x&(-x);
}
inline void updx(ll x,ll k){
while (x<=N) {
trx[x]=k;
ll low=lowbit(x);
for(int i=1;i<low;i<<=1){
trx[x]=min(trx[x-i],trx[x]);
}
x+=lowbit(x);
}
}
inline void updd(ll x,ll k){
while (x<=N) {
trd[x]=k;
ll low=lowbit(x);
for(int i=1;i<low;i<<=1){
trd[x]=max(trd[x-i],trd[x]);
}
x+=lowbit(x);
}
}
inline ll queryx(ll a,ll b){
ll res=1e18;
while (b>=a) {
res=min(H[b],res);
b-=1;
for(;b-lowbit(b)>=a;b-=lowbit(b)){
res=min(trx[b],res);
}
}
return res;
}
inline ll queryd(ll a,ll b){
ll res=0;
while (b>=a) {
res=max(H[b],res);
b-=1;
for(;b-lowbit(b)>=a;b-=lowbit(b)){
res=max(trd[b],res);
}
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>T;
FOR(i, 1, N){
cin>>H[i];
}
memset(trx, 0x3f, sizeof(trx));
FOR(i, 1, N){
updd(i, H[i]);
updx(i, H[i]);
}
while (T--) {
ll l,r;
cin>>l>>r;
cout<<queryd(l, r)-queryx(l, r)<<'\n';
}
return 0;
}
|