題意：給出n個互不相同的數字，要求一個最大的子段，使得該子段内所有數（除了兩端以外），值都在兩端的數字之間(比左端值大，比右端值小)。
分析：（http://www.cnblogs.com/rainydays/archive/2012/07/10/2584576.html）先對整個數組分别構造最大值RMQ和最小值RMQ的數組。然後，枚舉子段起點，對于每個起點求出這個起點是區間最小值的最遠終點（用二分查找）。然後在這個區間内找到最大值位置，從起點到最大值位置這個區間就是起點所對應的符合題意的最大區間。枚舉過所有的起點之後，結果就求出來了。其中二分還是比較靈活。如果不用hash的話，那麼rmq的時候儲存下标而不是值即可。
discuss裡有人說單調棧甚至暴搜也能AC。
#include <stdio.h>
#include <string.h>
#include <math.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define N 50005
int dmax[N][20],dmin[N][20],s[N],hash[100005];
int n;
void st(){
int i,j;
int k = log((double)n+1)/log(2.0);
for(i = 1;i<=n;i++)
dmax[i][0] = dmin[i][0] = s[i];
for(j = 1;j<=k;j++)
for(i = 1;i+(1<<j)-1<=n;i++)
dmax[i][j] = max(dmax[i][j-1], dmax[i+(1<<(j-1))][j-1]),
dmin[i][j] = min(dmin[i][j-1], dmin[i+(1<<(j-1))][j-1]);
}
int querymin(int a,int b){
int k = log((double)(b-a+1))/log(2.0);
return min(dmin[a][k], dmin[b-(1<<k)+1][k]);
}
int querymax(int a,int b){
int k = log((double)(b-a+1))/log(2.0);
return max(dmax[a][k], dmax[b-(1<<k)+1][k]);
}
int search(int x,int low,int high){
int j,mid;
int base = low-1;
while(low <= high){
mid = (low+high)>>1;
j = querymin(base,mid);
if(j < x)
high = mid-1;
else
low = mid+1;
}
return high;
}
int main(){
while(scanf("%d",&n) != EOF){
int i,j,end,res=0;
memset(hash,0,sizeof(hash));
for(i = 1;i<=n;i++){
scanf("%d",&s[i]);
hash[s[i]] = i;//由于這些數各不相同，是以可以用hash
}
st();
for(i = 1;i<n;i++){
end = search(s[i],i+1,n);//這個二分還是比較靈活的
j = hash[querymax(i,end)]-i;
res = max(res,j);
}
printf("%d\n",(!res)?-1:res);
}
return 0;
}
不用hash，rmq儲存下标：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 50005
#define M 100005
int s[N],n,dmin[N][20],dmax[N][20];
void st(int n){
int i,j,k = log((double)n)/log(2.);
for(i = 1;i<=n;i++)
dmin[i][0] = dmax[i][0] = i;
for(j = 1;j<=k;j++)
for(i = 1;i+(1<<j)-1<=n;i++){
if(s[dmin[i][j-1]] < s[dmin[i+(1<<(j-1))][j-1]])
dmin[i][j] = dmin[i][j-1];
else
dmin[i][j] = dmin[i+(1<<(j-1))][j-1];
if(s[dmax[i][j-1]] > s[dmax[i+(1<<(j-1))][j-1]])
dmax[i][j] = dmax[i][j-1];
else
dmax[i][j] = dmax[i+(1<<(j-1))][j-1];
}
}
int qmax(int a,int b){
int k = log((double)(b-a+1))/log(2.);
if(s[dmax[a][k]] < s[dmax[b-(1<<k)+1][k]])
return dmax[b-(1<<k)+1][k];
return dmax[a][k];
}
int qmin(int a,int b){
int k = log((double)(b-a+1))/log(2.);
if(s[dmin[a][k]] > s[dmin[b-(1<<k)+1][k]])
return dmin[b-(1<<k)+1][k];
return dmin[a][k];
}
int search(int b,int low,int high){
int mid;
while(low <= high){
mid = (low+high)>>1;
if(s[qmin(low,mid)] < b)
high = mid-1;
else
low = mid+1;
}
return high;
}
int main(){
while(scanf("%d",&n)!=EOF){
int i,j;
int res = -1;
for(i = 1;i<=n;i++)
scanf("%d",&s[i]);
st(n);
for(i = 1;i<n;i++){
j = search(s[i],i+1,n);
int tmp = qmax(i,j);
res = max(res,tmp-i);
}
printf("%d\n",!res?-1:res);
}
return 0;
}