社区讨论
为什么TLE了?
P3865【模板】ST 表 & RMQ 问题参与者 5已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mhj3jiuu
- 此快照首次捕获于
- 2025/11/03 20:08 4 个月前
- 此快照最后确认于
- 2025/11/03 20:08 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N][22];
int query(int l, int r){//查找两区间
int j = log2(r - l + 1);//区间长度的指数
return max(f[l][j], f[r - (1 << j) + 1][j]);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> f[i][0];
}
for(int j = 1; j <= log2(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, l, r; i <= m; i++){
cin >> l >> r;
cout << query(l, r) << endl;
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...