|
|
题目链接：http://poj.org/problem?id=2452
  /**//*
 题意：
给定一个长度为N(N <= 50000)的数列Si，要求找到Si和Sj(1 <= i < j <= N)
使得所有的Sk(i < k < j)大于Si并且小于Sj。如果能找到这样的对数，输出最大的
j-i，否则输出-1。
解法：
二分+线段树 或者 二分+RMQ
思路：
首先考虑最暴力的情况，自然是枚举i和j，然后判i+1到j-1这些数是否满足条件，
如果满足则更新j-i，这样的复杂度是O(n^3)的，时间上显然说不过去。然后试着降掉
一维，同样枚举i和j，然后在判断是否满足条件时，利用线段树求区间最值，这样的复
杂度就降到了O(n^2logn)，然而N的数据量还是不允许我们这么做，于是只能试着寻找
O(nlogn)的算法。
那么我们尝试枚举一个j，看看能不能通过它来确定i，这里有一条很明显的性质，
就是如果Si到Sj-1都小于Sj那么Si+1到Sj-1必然也都小于Sj，这条性质可以让我们二分
枚举i的左边界t，采用二分找到最小的t使得St-1 >= Sj，也即St < Sj(t <= i < j)，
找的过程可以采用线段树求出区间最大值进行比较，然后问题就转化成了在以下数列：
St St+1  Sj-1 Sj 找到最小的i(t <= i < j)使得Si+1到Sj都大于Si，很明显，又
是一个区间最值的问题，利用线段树求出[t, j-1]最小值的下标，就是我们要求的i，
如果有多个，必须选择最靠近j的，这是显然的。这样总的复杂度就降到O(n(logn)^2)，
当然求最值的时候可以采用RMG代替线段树，RMG的询问复杂度是O(1)的。
 */
 #include <iostream>
using namespace std;
#define maxn 50010
typedef int Tree_Index;
struct Tree {
int Max, Min;
int MinPos; // 最小值所在位置，相同的取靠右边的
// 区间最值
}T[4*maxn];
int val[maxn], n;
void Build(Tree_Index p, int l, int r) {
  if(l == r) {
T[p].Max = T[p].Min = val[l];
T[p].MinPos = l;
return ;
 }
int mid = (l + r) >> 1;
Build( p<<1, l, mid);
Build(p<<1|1, mid+1, r);
T[p].Max = T[p<<1].Max > T[p<<1|1].Max ? T[p<<1].Max : T[p<<1|1].Max;
T[p].Min = T[p<<1].Min < T[p<<1|1].Min ? T[p<<1].Min : T[p<<1|1].Min;
T[p].MinPos = T[p<<1].Min < T[p<<1|1].Min ? T[p<<1].MinPos : T[p<<1|1].MinPos;
}
Tree_Index Query(Tree_Index p, int l, int r, int a, int b, bool bMin) {
if(l == a && b == r) {
return p;
}
int mid = (l + r) >> 1;
if(b <= mid) {
return Query(p<<1, l, mid, a, b, bMin);
}else if(a >= mid + 1) {
return Query(p<<1|1, mid+1, r, a, b, bMin);
}else {
Tree_Index p1 = Query(p<<1, l, mid, a, mid, bMin);
Tree_Index p2 = Query(p<<1|1, mid+1, r, mid+1, b, bMin);
if(bMin) {
return T[p1].Min < T[p2].Min ? p1 : p2;
}else
return T[p1].Max > T[p2].Max ? p1 : p2;
}
}
int binary(int rIdx) {
int l = 1;
int r = rIdx;
int m;
int ans = rIdx;
while(l <= r) {
m = (l + r) >> 1;
if(m == rIdx) {
l = m + 1;
continue;
}
Tree_Index ansIdx = Query(1, 1, n, m, rIdx-1, false);
if(T[ansIdx].Max < val[rIdx]) {
r = m - 1;
if(m < ans) {
ans = m;
}
}else
l = m + 1;
}
return ans;
}
int main() {
int i;
while(scanf("%d", &n) != EOF) {
for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
Build(1, 1, n);
int Max = -1;
for(i = n; i >= 2; i--) {
int v = binary(i);
if(v != i) {
if(i - v < Max)
continue;
Tree_Index p = Query(1, 1, n, v, i, true);
if(T[p].MinPos != i) {
if(i - T[p].MinPos > Max)
Max = i - T[p].MinPos;
}
}
}
printf("%d\n", Max);
}
return 0;
}
|