O(n)RMQ四毛子

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

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

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

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

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

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

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

总结一下思路

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

#include
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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

参考：CSP2021-S 初赛