考虑分块
令
b
=
log
2
n
2
b=\frac{\log_2 n}2
b=2log2n,按
b
b
b 分块
使用ST表处理大块间的 RMQ 问题
对于一个块内的 RMQ 问题,由于差分数组
2
b
−
1
2^{b−1}
2b−1 种,可以预处理出所有情况下的最值位置
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;
}
}
}
}