题目大意

给你一个序列,叫你找出该序列中的一个最长连续子序列[left,right]使得a[left]为这段序列的最小值,a[right]为这段序列的最大值。

问题分析

首先假设当前存在区间[l,r],那么如果我们能用O(1)的时间返回这个区间的最大值所处位置a,以及最小值所处位置b,如果a<b的话区间[a,b]就是一组可行解,然后再分别递归调用[l,a-1] ,以及[b+1,r]即可,如果a>b,则对三段分别进行递归调用即可解决问题。那么,我们需要怎么样事先处理好区间[l,r]的最大值呢?

RMQ问题的ST算法

这就是一个经典的RMQ问题(Range Minimum/Maximum Query),我们采用ST算法也就是倍增来解决。用f[i][j]表示从i开始长度为2^j的区间的最小值,那么很容易得出状态转移方程:$f[i][j]=min{f[i][j-1],f[i+(1<<(j-1))][j-1]}​$,这样一来只需要O(nlogn)的时间就可以求出一个区间的最值了。接下来就是查询,我们令k为满足2^k<=R-L+1的最大整数,则以L为开头,以R为结尾的两个长度为2^k的区间合并起来即覆盖了查询区间[L,R],$k=trunc(log(R-L+1))​$,最后的查询结果即为$min{f[L][k],f[R-(1<<k)+1][k]}​$.

预处理代码

void RMQ_init()
{
	for(int i=1;i<=n;i++)
		f[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

查询代码

int find(int L,int R)
{
	int k=trunc(log2(R-L+1));
	return min(f[L][k],f[R-(1<<k)+1][k]);
}