记录编号	489204	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十二]奶牛排队	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.449 s
提交时间	2018-02-28 06:26:46	内存使用	1.30 MiB

#include <bits/stdc++.h>
 
const int MAXN=1e5+10;
 
int n;
int a[MAXN];
int r[MAXN];
std::pair<int,int> c[MAXN];
std::pair<int,int> data[MAXN];
 
int LowBit(int);
std::pair<int,int> Query(int);
void Add(int,std::pair<int,int>);
 
int main(){
#ifndef ASC_LOCAL
    freopen("tahort.in","r",stdin);
    freopen("tahort.out","w",stdout);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    std::stack< std::pair<int,int> > s;
    for(int i=1;i<=n;i++){
        while(!s.empty()&&s.top().first>=a[i]){
            r[s.top().second]=i-1;
            s.pop();
        }
        s.push(std::make_pair(a[i],i));
    }
    while(!s.empty()){
        r[s.top().second]=n;
        s.pop();
    }
    for(int i=1;i<=n;i++){
        data[i]=std::make_pair(r[i],i);
    }
    std::sort(data+1,data+n+1);
    int now=1,i=1;
    int ans=0;
    while(now<=n&&i<=n){
        while(i<=data[now].first){
            // printf("n=%d i=%d\n",now,i);
            Add(i,std::make_pair(a[i],i));
            ++i;
        }
        while(data[now].first<=i&&now<=n){
            // printf("n=%d i=%d\n",now,i);
            ans=std::max(ans,Query(data[now].second).second-data[now].second+1);
            ++now;
        }
    }
    if(ans==1)
        ans=0;
    printf("%d\n",ans);
    return 0;
}
 
inline void Add(int x,std::pair<int,int> d){
    x=n-x+1;
    while(x<=n){
        c[x]=std::max(c[x],d);
        x+=LowBit(x);
        // puts("A");
    }
}
 
inline std::pair<int,int> Query(int x){
    std::pair<int,int> ans=std::make_pair(0,0);
    x=n-x+1;
    while(x>0){
        ans=std::max(ans,c[x]);
        x-=LowBit(x);
    }
    return ans;
}
 
inline int LowBit(int x){
    return x&-x;
}