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
| #include<bits/stdc++.h>
using namespace std;
template <typename T>
class ST{
public:
const int n;
vector<vector<T>> st;
ST(int n = 0, vector<T> &a = {}) : n(n){
st = vector(n + 1, vector<T>(22 + 1));
build(n, a);
}
inline T get(const T &x, const T &y){
return max(x, y);
}
void build(int n, vector<T> &a){
for(int i = 1; i <= n; i++){
st[i][0] = a[i];
}
for(int j = 1, t = 2; t <= n; j++, t <<= 1){
for(int i = 1; i <= n; i++){
if(i + t - 1 > n) break;
st[i][j] = get(st[i][j - 1], st[i + (t >> 1)][j - 1]);
}
}
}
inline T find(int l, int r){
int t = log(r - l + 1) / log(2);
return get(st[l][t], st[r - (1 << t) + 1][t]);
}
};
int main() {
int n,q;
cin >> n >> q;
vector<int> f(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> f[i];
}
ST<int> st(n,f);
while (q--) {
int l, r;
cin >> l >> r;
cout <<st.find(l,r) << endl;
}
}
|