期望\(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;
}