社区讨论

49,求调

__WHMG_
P3865【模板】ST 表 & RMQ 问题参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lrgdaw2i
此快照首次捕获于
2024/01/16 21:06
2 年前
此快照最后确认于
2024/01/17 09:02
2 年前
查看原帖
C
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q,A[N],st[N][20];
inline void Pre(){
	for(int i=1;i<=n;i++) st[i][0]=A[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
inline int ask(int l,int r){
	int j=__lg(r-l+1);
	return max(st[l][j],st[r-(1<<j)+1][j]);
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>A[i];
	Pre();
	for(int i=1;i<=n;i++){
		int r,l;
		cin>>l>>r;
		cout<<ask(l,r)<<'\n';
	}
	return 0;
}

回复

共 5 条回复，欢迎继续交流。

正在加载回复...