|
|
題目鏈接：http://poj.org/problem?id=2452
  /**//*
 題意：
給定一個(gè)長度為N(N <= 50000)的數(shù)列Si，要求找到Si和Sj(1 <= i < j <= N)
使得所有的Sk(i < k < j)大于Si并且小于Sj。如果能找到這樣的對數(shù)，輸出最大的
j-i，否則輸出-1。
解法：
二分+線段樹 或者 二分+RMQ
思路：
首先考慮最暴力的情況，自然是枚舉i和j，然后判i+1到j(luò)-1這些數(shù)是否滿足條件，
如果滿足則更新j-i，這樣的復(fù)雜度是O(n^3)的，時(shí)間上顯然說不過去。然后試著降掉
一維，同樣枚舉i和j，然后在判斷是否滿足條件時(shí)，利用線段樹求區(qū)間最值，這樣的復(fù)
雜度就降到了O(n^2logn)，然而N的數(shù)據(jù)量還是不允許我們這么做，于是只能試著尋找
O(nlogn)的算法。
那么我們嘗試枚舉一個(gè)j，看看能不能通過它來確定i，這里有一條很明顯的性質(zhì)，
就是如果Si到Sj-1都小于Sj那么Si+1到Sj-1必然也都小于Sj，這條性質(zhì)可以讓我們二分
枚舉i的左邊界t，采用二分找到最小的t使得St-1 >= Sj，也即St < Sj(t <= i < j)，
找的過程可以采用線段樹求出區(qū)間最大值進(jìn)行比較，然后問題就轉(zhuǎn)化成了在以下數(shù)列：
St St+1  Sj-1 Sj 找到最小的i(t <= i < j)使得Si+1到Sj都大于Si，很明顯，又
是一個(gè)區(qū)間最值的問題，利用線段樹求出[t, j-1]最小值的下標(biāo)，就是我們要求的i，
如果有多個(gè)，必須選擇最靠近j的，這是顯然的。這樣總的復(fù)雜度就降到O(n(logn)^2)，
當(dāng)然求最值的時(shí)候可以采用RMG代替線段樹，RMG的詢問復(fù)雜度是O(1)的。
 */
 #include <iostream>
using namespace std;
#define maxn 50010
typedef int Tree_Index;
struct Tree {
int Max, Min;
int MinPos; // 最小值所在位置，相同的取靠右邊的
// 區(qū)間最值
}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;
}
|