有一个长度为n的数组A，有m个询问，每次你需要回答在区间[L,R]内的数的最大值。
输入描述:
输入的第一行是两个整数n,m,表示数组长度和询问个数。
第二行n个元素，表示A数组。
接下来m行，每行两个整数L和R，表示一个区间。
输出描述:
对于每个询问，输出相应的结果。
示例1
输入
5 3
4 5 2 3 8
3 4
3 5
2 4
输出
3
8
5
说明
n,m<=10^5
st1.cppview raw1
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
| #include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int a[N];
int n, m;
int S[N][17];
int query(int L, int R){
int res = a[L];
int step = R-L +1;
for(int i=0;(1<<i)<=step;i++){
if(step & (1<<i)){
res = max(res, S[L][i]);
L += (1<<i);
}
}
return res;
}
int main(){
scanf("%d%d", &n,&m);
for(int i=1;i<=n;i++) {
scanf("%d", &a[i]);
S[i][0] = a[i];
}
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++) {
int t = i + (1<<j-1);
S[i][j] = max(S[i][j-1], S[t][j-1]);
}
while(m--){
int L, R;
scanf("%d%d", &L, &R);
printf("%d\n", query(L, R));
}
return 0;
}
|
st2.cppview raw1
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
| #include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int a[N];
int n, m;
int S[N][17];
int query(int L, int R){
int k=0;
int res = 0;
while(L+(1<<k)<R-(1<<k)+1) k++;
res = max(S[L][k], S[R-(1<<k)+1][k]);
return res;
}
int main(){
scanf("%d%d", &n,&m);
for(int i=1;i<=n;i++) {
scanf("%d", &a[i]);
S[i][0] = a[i];
}
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++) {
int t = i + (1<<j-1);
S[i][j] = max(S[i][j-1], S[t][j-1]);
}
while(m--){
int L, R;
scanf("%d%d", &L, &R);
printf("%d\n", query(L, R));
}
return 0;
}
|
st3.cppview raw1
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
| #include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int a[N];
int n, m;
int S[N][17];
int Log[N];
int query(int L, int R){
int k= Log[R-L+1];
int res = max(S[L][k], S[R-(1<<k)+1][k]);
return res;
}
int main(){
scanf("%d%d", &n,&m);
for(int i=1;i<=n;i++) {
scanf("%d", &a[i]);
S[i][0] = a[i];
}
Log[0] =-1;
for(int i=1;i<=n;i++) Log[i] = Log[i>>1] + 1;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++) {
int t = i + (1<<j-1);
S[i][j] = max(S[i][j-1], S[t][j-1]);
}
while(m--){
int L, R;
scanf("%d%d", &L, &R);
printf("%d\n", query(L, R));
}
return 0;
}
|