社区讨论

为什么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 条回复,欢迎继续交流。

正在加载回复...