题目
https://www.luogu.com.cn/problem/P3865
给定一个长度为N的数列和M次询问，求出每一次询问的区间内数字最大值。
令f[i][j]表示区间$[i, i + 2^j - 1]$的最大值。根据倍增的思想，可以写出状态转移方程$f[i][j] = max(f[i][j - 1], f[i + 2^{j - 1}][j - 1])$
因此对于每个询问[l, r]，我们将其分为两部分$[l, l + 2^s - 1], [r - 2^s + 1, r]$，其中$s = log_2(r - l + 1)$
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
| #include<bits/stdc++.h>
using namespace std;
static constexpr int MAXN = 1e5 + 5;
int f[MAXN][21];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, m, l, r, s;
cin >> n >> m;
vector<int> arr(n, 0);
for (int i = 0; i < n; i++) {
cin >> arr[i];
f[i][0] = arr[i];
}
for (int j = 1; j <= 20; j++) {
for (int i = 0; i + (1 << (j - 1)) < n; i++) {
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 0; i < m; i++) {
cin >> l >> r;
s = log2(r - l + 1);
cout << max(f[l][s], f[r - (1 << s) + 1][s]) << endl;
}
return 0;
}
|