今天我和机房同学打赌,说这题可以用树状数组写。让后我就去写了，然后过了，我把它分享给大家（大号被禁言了）

提交记录

code:

#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;
}
int n,m,l,r;
int maxn[200005],a[200005];
int lowbit(int x){return x&(-x);}
int main(){
	freopen("P3865.in","r",stdin);
	freopen("P3865.out","w",stdout);
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		for(int j=i;j<=n&&j>0;j+=lowbit(j))
			maxn[j]=max(a[i],maxn[j]);
	}
	for(int i=1;i<=m;i++){
		l=read();
		r=read();
		int ans=0;
		while(1){
			if(l>=r)break;
			while(1){
			//	printf("%d ",r);
				if(r-lowbit(r)<l)break;
				ans=max(maxn[r],ans);
				r-=lowbit(r);
			}
			ans=max(a[r],ans);
			r--;
		}
		printf("%d\n",max(ans,a[l]));
	}
}