ST表板子

ST表在离线查找RMQ问题时的复杂度较小，偷个板子来。

预处理，O(nlogn)，查询：O(1)

Code：

class ST{
	ll STmax[MAXN][20],STmin[MAXN][20],mn[MAXN];
	
	public : void IntST(int n,ll a[]){
		mn[0]=-1;
		for(int i=1;i<=n;++i){
			mn[i]=((i&(i-1))==0)?mn[i-1]+1:mn[i-1];
			STmax[i][0]=STmin[i][0]=a[i];
		}
		for(int j=1;j<=mn[n];++j){
			for(int i=1;i+(1<<j)-1<=n;++i){
				STmax[i][j]=max(STmax[i][j-1],STmax[i+(1<<(j-1))][j-1]);
				STmin[i][j]=min(STmin[i][j-1],STmin[i+(1<<(j-1))][j-1]);
			}
		}
	}
	public : ll RMQMAX(int l,int r){
		int k=mn[r-l+1];
		return max(STmax[l][k],STmax[r-(1<<k)+1][k]);
	}
	public : ll RMQMIN(int l,int r){
		int k=mn[r-l+1];
		return min(STmin[l][k],STmin[r-(1<<k)+1][k]);
	}
};