问题：区间最大值（下标从 $0$ 开始）。

从2021 CSP-S 初赛最后一题抄来的 the Method of Four Russians。

#include<iostream>
#include<cmath>
using namespace std;
const int MAXN=100000,MAXT=MAXN<<1,MAXL=18,MAXB=9,MAXC=MAXT/MAXB;
struct node{
	int val,dep,dfn,end;
	node *son[2];
}T[MAXN];
int m,n,t,b,c,Log2[MAXC+1],Pos[(1<<(MAXB-1))+5],Dif[MAXC+1];
node *root,*A[MAXT],*Min[MAXL][MAXC];
void build(){
	static node *S[MAXN+1];
	int top=0;
	for(int i=0;i<n;i++){
		node *p=&T[i];
		while(top&&S[top]->val<p->val){
			p->son[0]=S[top--];
		}
		if(top){
			S[top]->son[1]=p;
		}
		S[++top]=p;
	}
	root=S[1];
	return;
}
void DFS(node *p){
	A[p->dfn=t++]=p;
	for(int i=0;i<2;i++){
		if(p->son[i]){
			p->son[i]->dep=p->dep+1;
			DFS(p->son[i]);
			A[t++]=p;
		}
	}
	p->end=t-1;
	return;
}
node *min(node *x,node *y){
	return x->dep<y->dep?x:y;
}
void ST_init(){
	b=(int)(ceil(log2(t)/2));
	c=t/b;
	Log2[1]=0;
	for(int i=2;i<=c;i++){
		Log2[i]=Log2[i>>1]+1;
	}
	for(int i=0;i<c;i++){
		Min[0][i]=A[i*b];
		for(int j=1;j<b;j++){
			Min[0][i]=min(Min[0][i],A[i*b+j]);
		}
	}
	for(int i=1,l=2;l<=c;i++,l<<=1){
		for(int j=0;j+l<=c;j++){
			Min[i][j]=min(Min[i-1][j],Min[i-1][j+(l>>1)]);
		}
	}
	return;
}
void small_init(){
	for(int i=0;i<=c;i++){
		for(int j=1;j<b&&i*b+j<t;j++){
			if(A[i*b+j]->dep<A[i*b+j-1]->dep){
				Dif[i]|=1<<(j-1);
			}
		}
	}
	for(int S=0;S<(1<<(b-1));S++){
		int mx=0,v=0;
		for(int i=1;i<b;i++){
			v+=(S>>(i-1)&1)?-1:1;
			if(v<mx){
				mx=v;
				Pos[S]=i;
			}
		}
	}
	return;
}
node *ST_query(int l,int r){
	int g=Log2[r-l+1];
	return min(Min[g][l],Min[g][r-(1<<g)+1]);
}
node *small_query(int l,int r){
	int p=1/b;
	int S=(Dif[p]>>(1-p*b))&((1<<(r-l))-1);
	return A[l+Pos[S]];
}
node *query(int l,int r){
	if(l>r)return query(r,l);
	int pl=l/b,pr=r/b;
	if(pl==pr){
		return small_query(l,r);
	}else{
		node *s=min(small_query(l,pl*b+b-1),small_query(pr*b,r));
		if(pl+1<=pr-1){
			s=min(s,ST_query(pl+1,pr-1));
		}
		return s;
	}
}
signed main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>T[i].val;
	}
	build();
	DFS(root);
	ST_init();
	small_init();
	while(m--){
		int l,r;
		cin>>l>>r;
		cout<<query(T[l].dfn,T[r].dfn)->val<<endl;
	}
	return 0;
}

但是对于这组数据会出错：

10 1
-75 -30 -100 -38 -50 -51 -52 -20 -81 -5
2 4

样例输出：

-38

实际输出：

-100

谢谢了！

另：原试题在这里