本人按照论文写了个树状数组，结果 A 了，最大点 298ms。

求分析理论时间复杂度。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int N = 1000010; int tr1[N], tr2[N], n, q;
int a[N];
int lbt(int x) {return x & -x;}
int ask(int l, int r) {
	int mx = 0, x = l, y = r;
	for(int i = l; i + lbt(i) - 1 <= r; i += lbt(i)) {
//		cout << "i = " << i << '\n',
		mx = max(mx, tr2[i]);
		x = i + lbt(i) - 1;
	}
	for(int i = r; i - lbt(i) >= l; i -= lbt(i)) {
//		cout << "ii = " << i << '\n',
		mx = max(mx, tr1[i]);
		y = i - lbt(i) + 1;
	}
	for(int i = x; i <= y; i++) mx = max(mx, a[i]);
	return mx;
}
void chg(int x, int k) {
	for(int i = x; i <= n; i += lbt(i)) tr2[i] = max(tr2[i], k);
	for(int i = x; i; i -= lbt(i)) tr1[i] = max(tr1[i], k);
}
int main() {
	cin >> n >> q; int x;
	for(int i = 1; i <= n; i++) a[i] = read();
	for(int i = 1; i <= n; i++) {
		for(int j = i - lbt(i) + 1; j <= i; j++) tr1[i] = max(tr1[i], a[j]);
		for(int j = i; j <= i + lbt(i) - 1 && j <= n; j++) tr2[i] = max(tr2[i], a[j]);
//		cout << tr1[i] << ' ' << tr2[i] << '\n';
	}
	while(q--) {
		int l, r; l = read(), r = read();
		cout << ask(l, r) << '\n';
	}
	return 0;
}