±1 RMQ

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

考虑分块

令 $b=\frac{\log_2 n}2$ ，按 $b$ 分块

使用ST表处理大块间的 RMQ 问题

对于一个块内的 RMQ 问题，由于差分数组 $2^{b−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; 
			}
		}	
	}
}