社区讨论
为什么ios::sync_with_stdio(false); 这个万能方法都过不了……
P3865【模板】ST 表 & RMQ 问题参与者 9已保存回复 12
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 12 条
- 当前快照
- 1 份
- 快照标识符
- @mi6ldoru
- 此快照首次捕获于
- 2025/11/20 06:46 4 个月前
- 此快照最后确认于
- 2025/11/20 07:00 4 个月前
···
CPP#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int N, M, a[100010], f[100010][20];
//定义f[i][j]为i到i+2^j-1区间的最大值
void prepar()
{
for (int i = 1; i <= N; i++) f[i][0] = a[i];
for (int j = 1; (1 << j) <= N; j++)
for (int i = 1; i + (1 << j) - 1 <= N; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}//二分来预处理,时间复杂度O(nlogn)
CPPint getans(int l, int r)
{
int k = int(log(r - l + 1) / log(2));
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
ios::sync_with_stdio(false);
cin >> N >> M;
for (int i = 1; i <= N; i++)
cin >> a[i];
prepar();
while (M--)
{
int l, r;
cin >> l >> r;
cout << getans(l, r) << endl;
}
return 0;
}
···
回复
共 12 条回复,欢迎继续交流。
正在加载回复...