洛谷 P3865 【模板】ST表
题目链接 https://www.luogu.org/problem/P3865
分析 【洛谷 P3865 【模板】ST表】ST表使用倍增思想，一般用于解决O ( n l o g n ) O(nlogn) O(nlogn) 预处理， O ( 1 ) O(1) O(1) 查询的静态区间最值问题。
AC代码
#include
#include using namespace std;
inline int read() {
int num = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9')
num = num * 10 + c - '0', c = getchar();
return num;
}const int maxn = 1e5 + 5;
int f[maxn][20], k[maxn];
int main() {
int n = read(), m = read();
k[0] = -1;
for (int i = 1;
i <= n;
++i) f[i][0] = read(), k[i] = k[i / 2] + 1;
for (int j = 1;
j <= k[n];
++j)
for (int i = 1;
i <= n - (1 << j) + 1;
++i)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
for (int i = 1;
i <= m;
++i) {
int l = read(), r = read();
int j = k[r - l + 1];
printf("%d\n", max(f[l][j], f[r - (1 << j) + 1][j]));
}
return 0;
}
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长