# Sticks Problem POJ – 2452 （线段树）

Sticks Problem
 Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 10724 Accepted: 2855

Description

Xuanxuan has n sticks of different length. One day, she puts all her sticks in a line, represented by S1, S2, S3, …Sn. After measuring the length of each stick Sk (1 <= k <= n), she finds that for some sticks Si and Sj (1<= i < j <= n), each stick placed between Si and Sj is longer than Si but shorter than Sj.

Now given the length of S1, S2, S3, …Sn, you are required to find the maximum value j – i.

Input

The input contains multiple test cases. Each case contains two lines.
Line 1: a single integer n (n <= 50000), indicating the number of sticks.
Line 2: n different positive integers (not larger than 100000), indicating the length of each stick in order.

Output

Output the maximum value j – i in a single line. If there is no such i and j, just output -1.

Sample Input

4
5 4 3 6
4
6 5 4 3


Sample Output

1
-1

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[50007];
int t;
int b[150007];
int bb[150007];
int c[150007];
int cc[150007];
int max(int a,int b){
return a>b?a:b;
}
int min(int a,int b){
return a<b?a:b;
}
void build(int num,int l,int r){
if(l==r){
b[num]=a[l];
c[num]=a[r];
bb[num]=cc[num]=l;
return;
}
build(num<<1,l,(l+r)/2);
build(1+(num<<1),((l+r)/2)+1,r);
b[num]=max(b[num<<1],b[1+(num<<1)]);
c[num]=min(c[num<<1],c[1+(num<<1)]);
if(b[num<<1]>b[1+(num<<1)]){
bb[num]=bb[num<<1];
}else{
bb[num]=bb[1+(num<<1)];
}
if(c[num<<1]<c[1+(num<<1)]){
cc[num]=cc[num<<1];
}else{
cc[num]=cc[1+(num<<1)];
}
return;
}
int maxnum(int num,int L,int R,int l,int r){
//cout<<num<<" "<<L<<" "<<R<<" "<<endl;

if(l<=L&&r>=R){
//	cout<<num<<" "<<bb[num]<<endl;
return bb[num];
}
int mid=(L+R)/2;
int loc=0;
if(l<=mid){
loc=maxnum(num<<1,L,(R+L)/2,l,r);
//	cout<<"loc"<<loc<<
}
if(r>mid){
if(loc){
int temloc=maxnum(1+(num<<1),mid+1,R,l,r);
if(a[loc]<a[temloc]){
//	cout<<a[loc]<<" 1 1 1 "<<a[temloc]<<endl;
loc=temloc;
}
}else{
loc=maxnum(1+(num<<1),mid+1,R,l,r);
}
}
return loc;

}
int minnum(int num,int L,int R,int l,int r){

if(l<=L&&r>=R){
return cc[num];
}
int mid=(L+R)/2;
int loc=0;
if(l<=mid){
loc=minnum(num<<1,L,(R+L)/2,l,r);

}
if(r>mid){
if(loc){
int temloc=minnum(1+(num<<1),mid+1,R,l,r);
if(a[loc]>a[temloc]){
loc=temloc;
}
}else{
loc=minnum(1+(num<<1),mid+1,R,l,r);
}
}
return loc;
}
int sum(int l,int r){
if(r<=l||r>t||l<1){
return -1;
}

int maxi=maxnum(1,1,t,l,r);
int mini=minnum(1,1,t,l,r);
//	cout<<maxi<<" "<<mini<<" "<<l<<" "<<r<<endl;
if(maxi>mini){
int len=maxi-mini;
len=max(len,sum(l,mini-1));
len=max(len,sum(maxi+1,r));
return len;
}
if(maxi<mini){
int len=sum(maxi+1,mini-1);
len=max(len,sum(l,maxi));
len=max(len,sum(mini,r));
return len;
}else{
return -1;
}
}
int main()
{
ios::sync_with_stdio(0);
while(cin>>t){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
memset(bb,0,sizeof(bb));
memset(cc,0,sizeof(cc));
for(int i=1;i<=t;i++){
cin>>a[i];
}
build(1,1,t);

//cout<<minnum(1,1,t,1,2);

cout<<sum(1,t)<<endl;

}

return 0;
}