BZOJ2457 BeiJing2011 双端队列

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 const int maxn=200010;
 8 
 9 struct Node{
10     int x,pos;
11 }a[maxn];
12 
13 int n,cnt,ans;
14 int Max[maxn],Min[maxn];
15 
16 bool cmp(const Node &A,const Node &B){
17     if(A.x!=B.x) return A.x<B.x;
18     return A.pos<B.pos;
19 }
20 
21 int main(){
22 #ifndef ONLINE_JUDGE
23     freopen("x.in","r",stdin);
24 #endif
25     scanf("%d",&n);
26     for(int i=1;i<=n;i++)
27         scanf("%d",&a[i].x),a[i].pos=i;
28     sort(a+1,a+n+1,cmp);
29     
30     for(int i=1;i<=n;i++)
31          if(a[i].x!=a[i-1].x || i==1){
32                Max[cnt]=a[i-1].pos;
33                Min[++cnt]=a[i].pos;
34          }
35     Max[cnt]=a[n].pos;
36     
37     int h=0;bool b=false;
38     //h表示当前链末尾的 pos大小 ，b表示当前链是向上或者向下趋势。 
39     for(int i=1;i<=cnt;i++)
40         if(!b){
41             if(h>Max[i]) h=Min[i];
42             else h=Max[i],b=true;
43         }
44         else{
45             if(h<Min[i]) h=Max[i];
46             else ans++,h=Min[i],b=false;
47         }
48     
49     printf("%d",ans);
50     return 0;
51 }