【提示：本贴疑似讨论区题解】动态 push_back 的 ST 表？

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,m,st[N][20],bs[N];
int getmax(int l,int r) {
	return max(st[l][bs[r-l+1]],st[r-(1<<bs[r-l+1])+1][bs[r-l+1]]);
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=16;i++) {
		for(int j=(1<<i)+1;j<=min((1<<i+1),n);j++) bs[j]=i;
	}
	for(int i=1;i<=n;i++) {
		scanf("%d",&st[i][0]);
		for(int j=1;;j++) {
			if(i-(1<<j)<0) break;
			st[i-(1<<j)+1][j]=max(getmax(i-(1<<j)+1,i-1),st[i][0]);
		}
	}
	while(m--) {
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",getmax(x,y));
	}
	return 0;
}