倍增算法【模板】

原题链接https://www.luogu.com.cn/problem/P3865
题解链接https://blog.csdn.net/WJTF2/article/details/136239183?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522423e6dee0d2c53e9645ecba193312fb3%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=423e6dee0d2c53e9645ecba193312fb3&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_alltop_click~default-2-136239183-null-null.142^v101pc_search_result_base2&utm_term=st%E8%A1%A8

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
using ll = long long;
using pii = pair<char, int>;
const double PI = acos(-1);
const int N =1e5+10;
const int mod = 1e9 + 7;
ll st[N][30];
void solve(){
	ll n,m;cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>st[i][0];
	for(ll j=1;(1<<j)<=n;j++)//枚举区间长度
		for(int i=1;i+(1<<j)-1<=n;i++){//枚举2^i长度的可能的子区间
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	while(m--){
		ll l,r;cin>>l>>r;
		ll x=floor(log2(r-l+1));
		cout<<max(st[l][x],st[r-(1<<x)+1][x])<<endl;
	}
}
int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
//	cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}