有一种ST表,叫做±1ST表
这种ST表可以在
O
(
n
)
O(n)
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 初赛