O(n)RMQ四毛子

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132906644

有一种ST表，叫做±1ST表

这种ST表可以在 $O(n)$ 的时刻内完成建树

其本质就是分块，大块为整除的ST表，小块的差分数组种类不多，完全可以预处理

现在考虑推广到普通的ST表里

我们发现我们真正关心的是数之间的大小关系。但又要使相邻数之间差恰好为±1

考虑什么东西的差为1。树的欧拉环游序点之间的深度差！

现在需要数之间的大小关系，也需要树，那么，我们建笛卡尔树就行了！

总结一下思路

先建出笛卡尔树，求出其欧拉环游序，然后对其欧拉换有序的差进行±1RMQ即可。

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 400010
#define M 400010
//#define mo
struct node {
	int val; 
	int dep, dfn, end; 
	int son[2]; 
}T[N], Mn[N][20];
int n, m, i, j, k;
int l, r, top, q, rt; 
int Pos[N], Dif[N], a[N], Log2[N]; 
int b, c; 

int build() {
	int S[N]; 
	for(int i=1; i<=n; ++i) {
		while(top && T[S[top]].val < T[i].val) 
			T[i].son[0]=S[top], --top; 
		if(top) T[S[top]].son[1]=i; 
		S[++top]=i; 
	}
	top=0; 
	return S[1]; 
}

void dfs(int x) {
	a[top]=x; T[x].dfn=top; ++top;  
	for(int i=0; i<=1; ++i)
		if(T[x].son[i]) {
			int y=T[x].son[i]; 
//			printf("%d -> %d\n", x, y); 
			T[y].dep=T[x].dep+1; 
			dfs(y); 
			a[top++]=x; 
		}
	T[x].end=top-1; 
}

node max(node a, node b) {
	if(a.val>b.val) return a; 
	return b; 
}

node min(node a, node b) {
	if(a.val<b.val) return a; 
	return b; 
}

void pre_ST() {
	int i, j, k, l; 
	b=(int)(ceil(log2(top)/2)); c=top/b; 
	Log2[1]=0; 
	for(i=2; i<=top; ++i) Log2[i]=Log2[i>>1]+1; 
	for(i=0; i<c; ++i) {
		Mn[i][0]=T[a[i*b]]; 
		for(j=1; j<b; ++j) 
			Mn[i][0]=max(Mn[i][0], T[a[i*b+j]]); 
	}
	for(k=l=1; l<c; ++k, l<<=1)
		for(i=0, j=l; i+(l<<1)-1<top; ++i, ++j) {
			Mn[i][k]=max(Mn[i][k-1], Mn[j][k-1]); 
		}
}

void pre_small() {
	int i, j, s; 
	for(i=0; i<=c; ++i) {
		for(j=1; j<b && i*b+j<top; ++j)
			if(T[a[i*b+j]].dep<T[a[i*b+j-1]].dep)
				Dif[i]|=(1<<j-1); 
	}
	for(s=0; s<(1<<b-1); ++s) {
		int v=0, mx=0; Pos[s]=0; 
		for(i=1; i<b; ++i) {
			if(s&(1<<i-1)) --v; 
			else ++v; 
			if(v<mx) {
				mx=v; Pos[s]=i; 
			}
		}	
	}
}

node que_small(int l, int r) {
	int p=l/b; 
	int S=((Dif[p]>>(l-p*b))&((1<<r-l)-1)); 
	return T[a[l+Pos[S]]]; 
}

node que_ST(int l, int r) {
	int k=Log2[r-l+1]; 
	return max(Mn[l][k], Mn[r-(1<<k)+1][k]); 
}

int que(int l, int r) {
	if(l>r) return que(r, l); 
	if(l==r) return T[a[l]].val; 
	int pl=l/b, pr=r/b; 
	if(pl==pr) return que_small(l, r).val; 
	node ans=max(que_small(l, pl*b+b-1), que_small(pr*b, r)); 
	if(pl+1<=pr-1) ans=max(ans, que_ST(pl+1, pr-1)); 
	return ans.val; 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); q=read(); 
	for(i=1; i<=n; ++i) T[i].val=read(); 
	rt=build(); 
	dfs(rt); 
	pre_ST(); 
	pre_small(); 
	while(q--) {
		l=read(); r=read(); 
		printf("%d\n", que(T[l].dfn, T[r].dfn)); 
	}
	return 0;
}

参考：CSP2021-S 初赛