甚至数据太大下不了数据。

#include<cstdio>
#include<cmath>
using namespace std;
int n,m,bl,idj,idk;
int a[100001];
int st[320],ed[320],bel[1000001],siz[320];
int s1[320][330],s2[320][320],s3[320][320],s4[320][316*316+1];
int mp[320][320],tot;
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;
}
inline int max(int a,int b){return a>b?a:b;}
void init()
{
	bl=sqrt(n);
	for(int i=0;i<=bl+10;++i)
		for(int j=0;j<=bl+10;++j)
			mp[i][j]=tot++;
	for(int i=1;i<=bl;++i)
	{
		st[i]=n/bl*(i-1)+1,
		ed[i]=n/bl*i,
		siz[i]=ed[i]-st[i]+1;
		for(int j=st[i];j<=ed[i];++j)
			bel[j]=i;
	}
	ed[bl]=n;siz[bl]=ed[bl]-st[bl]+1;
	for(int j=st[bl];j<=ed[bl];++j)bel[j]=bl;
	for(int i=1;i<=bl;++i)
	{
		for(int j=st[i];j<=ed[i];++j)
		{
			idj=j%siz[i];
			s1[i][idj]=max(a[j],s1[i][idj-1>=0?idj-1:idj-1+siz[i]]);
		}
		for(int j=ed[i];j>=st[i];--j)
		{
			idj=j%siz[i];
			s2[i][idj]=max(a[j],s2[i][idj+1<siz[i]?idj+1:idj+1-siz[i]]);
		}
	}
	for(int i=1;i<=bl;++i)
		for(int j=i;j<=bl;++j)
			s3[i][j]=max(s3[i][j-1],s1[j][ed[j]%bl]);
	
	for(int i=1;i<=bl;++i)
		for(int j=st[i];j<=ed[i];++j)
		{
			idj=j%siz[i];
			for(int k=j;k<=ed[i];++k)
			{
				idk=k%siz[i];
				s4[i][mp[idj][idk]]=max(s4[i][mp[idj][idk-1>=0?idk-1:idk-1+siz[i]]],a[k]);
			}
		}
}
int query(int l,int r)
{
	if(bel[l]==bel[r])return s4[bel[l]][mp[l%siz[bel[l]]][r%siz[bel[l]]]];
	int ans=0;
	ans=max(ans,s2[bel[l]][l%siz[bel[l]]]);
	ans=max(ans,s1[bel[r]][r%siz[bel[r]]]);
	ans=max(ans,s3[bel[l]+1][bel[r]-1]);
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		a[i]=read();
	init();
	for(int i=1,l,r;i<=m;++i)
		l=read(),r=read(),printf("%d\n",query(l,r));
	return 0;
}

s1块内前缀max。

s2块内后缀max。

s3整块之间的max。

s4整块内部的max，第二维经过mp映射。