RMQ

时间复杂度 处理O(nlogn) 查询O(1)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define endl "\n"
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
const int base=131;
const int mod=1e9+7;
const int N=1e5+9,M=1e6+9;
int a[N],f[N],dp[N][30];
int n,m;
void RMQ()
{
	for(int j=1;j<=f[n];j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
void f0(int T)
{
	cin>>n>>m;
	f[0]=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>dp[i][0]; 
		f[i]=f[i>>1]+1;
	}
	RMQ();
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		int t=f[r-l+1];
		cout<<max(dp[l][t],dp[r-(1<<t)+1][t])<<endl; 
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T=1;
//	cin>>T;
	for(int i=1;i<=T;i++)
		f0(i);
	return 0;
}

原文地址：http://www.cnblogs.com/2021sgy/p/16811477.html