树状数组单次查询的复杂度已经飞到了 $O(log^2n)$ 还不如线段树 但是过去了。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
//ifstream fin("");
//ofstream fout("");
int a[1145141],C[1145141];
int lowbit(int x){return x&(-x);}
int getmax(int l, int r) {
	int ans = 0;
	while (r >= l) {
		ans = max(ans, a[r]);
		--r;
		for (; r - lowbit(r) >= l; r -= lowbit(r)) {
			
			ans = max(ans, C[r]);
		}
	}
	return ans;
}
int n,m,l,r;
void update(int i,int k)
{
	int lb;
	C[i]=a[i]=k;
	while(i<=n)
	{
		lb=lowbit(i);
		C[i]=a[i];
		for(int j=1;j<lb;j<<=1)
			C[i]=max(C[i],C[i-j]);
		i+=lowbit(i);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		update(i,a[i]);
	}
	while(m--){
		cin>>l>>r;
		cout<<getmax(l,r)<<'\n';
	}
	return 0;
}