s1块内前缀max。
s2块内后缀max。
s3整块之间的max。
s4整块内部的max，第二维经过mp映射。
by TempestJueMu @ 2022-08-22 14:36:11
呃
试试这个？
```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
#define INF_INT 0x3f3f3f3f
using namespace std;
const int N=5e5;
int Q,n,ans,block,num,x,y,p,q;
int a[N],bl[N],maxx[N],minn[N],l[N],r[N];
void build(){
block=sqrt(n);
num=n/block;
if(n%block)num++;
for(int i=1;i<=n;i++){
bl[i]=(i-1)/block+1;
}
for(int i=1;i<=num;i++)
l[i]=(i-1)*block+1,r[i]=i*block;
r[num]=n;
for(int i=1;i<=num;i++){
for(int j=l[i];j<=r[i];j++){
maxx[i]=max(a[j],maxx[i]);
minn[i]=min(a[j],minn[i]);
}
}
}
inline int ask_max(int x,int y){
ans=-1;
p=bl[x];
q=bl[y];
if(p==q){
for(int i=x;i<=y;i++)
ans=max(ans,a[i]);
return ans;
}
else{
for(int i=x;i<=r[p];i++)
ans=max(ans,a[i]);
for(int i=p+1;i<=q-1;i++)
ans=max(ans,maxx[i]);
for(int i=l[q];i<=y;i++)
ans=max(ans,a[i]);
return ans;
}
}
int main(){
// freopen("P1816_1.in","r",stdin);
// freopen("SB.out","w",stdout);
scanf("%d %d",&n,&Q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build();
while(Q--){
scanf("%d %d",&x,&y);
printf("%d\n",ask_max(x,y));
}
return 0;
}
```
by Tjqq @ 2022-10-22 22:09:30