期望\(O(n)-O(1)的RMQ\)
#include<bits/stdc++.h>
#define int long long
#define F(i0,i1,i2) for(int i0=(i1);i0<=(i2);++i0)
using namespace std;
inline int rd(){
int x=0,f=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return f?-x:x;
}
const int N=20000005,sN=4400,mod=1e9+7;
int a[N+sN+100],n,m,s;
int ans;
int blo,st[N/sN][sN+100],pre[N/sN][sN+100],suf[N/sN][sN+100],tot;
void build(){
blo=sqrt(n);
tot=(n-1)/blo;
F(i,0,n-1){
a[i]=read();
st[i/blo][0]=max(st[i/blo][0],a[i]);
}
F(i,1,__lg(tot))
for(int j=0;j+(1<<(i-1))<=tot;++j)st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
F(i,0,tot){
int st=i*blo;
pre[i][0]=a[st];
F(j,1,blo-1)pre[i][j]=max(pre[i][j-1],a[st+j]);
suf[i][blo-1]=a[st+blo-1];
for(int j=blo-2;j>=0;--j)suf[i][j]=max(suf[i][j+1],a[st+j]);
}
}
int que(int l,int r){
int bl=l/blo,br=r/blo;
int ans=0;
if(bl==br){
F(i,l,r)ans=max(ans,a[i]);
return ans;
}
ans=max(suf[bl][l%blo],pre[br][r%blo]);
int len=__lg(br-bl-1);
if(br-bl-1==0)return ans;
ans=max(ans,max(st[bl+1][len],st[br-(1<<len)][len]));
return ans;
}
signed main(){
return 0;
}