poj 2452(RMQ+二分)

解题思路：这题实际上就是求某区间上的最值问题，可以先枚举区间的起始位置，然后二分去搜索比起始位置大的数且位置最远（这里可以用RMQ算法区间内的最小值），找到之后再利用RMQ算法找这段区间内的最大的，如果这段区间的长度比当前的最优值大，那么更新。详细的见代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

const int maxn = 50005;
int n,stick[maxn],dp_max[maxn][20],dp_min[maxn][20];

int _max(int l,int r)
{
	if(stick[l] > stick[r]) return l;
	return r;
}

int _min(int l,int r)
{
	if(stick[l] < stick[r]) return l;
	return r;
}

void initRMQ()
{
	for(int i = 1; i <= n; i++)
		dp_max[i][0] = dp_min[i][0] = i;
	for(int j = 1; (1 << j) <= n; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
		{
			dp_max[i][j] = _max(dp_max[i][j-1],dp_max[i+(1<<j-1)][j-1]);
			dp_min[i][j] = _min(dp_min[i][j-1],dp_min[i+(1<<j-1)][j-1]);
		}
}

int MaxValue(int l,int r)
{
	int k = (int)(log(double(r) - l + 1) / log(2.0));  
	return _max(dp_max[l][k],dp_max[r-(1<<k)+1][k]);
}

int MinValue(int l,int r)
{
	int k = (int)(log(double(r) - l + 1) / log(2.0));  
	return _min(dp_min[l][k],dp_min[r-(1<<k)+1][k]);
}

int binsearch(int x,int l,int r)
{
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(stick[x] < stick[MinValue(l,mid)])
			l = mid + 1;
		else r = mid;
	}
	return l;
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i = 1; i <= n; i++)
			scanf("%d",&stick[i]);
		initRMQ();
		int ans = 0;
		for(int i = 1; i + ans < n; i++)
		{
			int r = binsearch(i,i+1,n);
			int k = MaxValue(i,r);
			if(stick[k] > stick[i])
				ans = max(ans,k - i);
		}
		if(ans == 0) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}