const int N = 200002;
typedef long long LL;
const int INF = 0x7fffffff;
LL a [N];
int b [N], mo [N][2], cnt;
inline bool cmp ( int x, int y ){
return a [x] < a [y];
}
int main (){
int n; rd ( n );
for ( int i = 1; i <= n; ++i ) lrd ( a [i] );
for ( int i = 1; i <= n; ++i ) b [i] = i;
sort ( b+1, b+n+1, cmp );
for ( int i = 1; i <= n; ){
int j = i; int mn = INF, mx = -INF;
while ( j <= n && a [ b [i] ] == a [ b [j] ] ){
mn = min ( mn, b [j] );
mx = max ( mx, b [j] );
j ++;
}
mo [++cnt][0] = mn; mo [cnt][1] = mx;
i = j;
}
mo [++cnt][0] = INF; mo [cnt][1] = INF;
mo [0][0] = mo [0][1] = INF;
int now = mo [0][0], ans = 0; bool d = true;
for ( int i = 1; i <= cnt; ++i ){
if ( d ){
if ( mo [i][1] < now ) now = mo [i][0];
else{ ans ++; d = false; now = mo [i][1]; }
}else{
if ( mo [i][0] > now ) now = mo [i][1];
else{ d = true; now = mo [i][0]; }
}
}
printf ( "%d", ans ); return 0;
}
//18 635 -79 -117 620 767 -340 -209 514 509 208 169 500 275 -88 -678 635 122 -220
注意20-24行,sort后不一定保证下标不变,当然也可以写个cmp函数(如下)。
inline bool cmp ( int x, int y ){
if ( a [x] == a [y] ) return x < y;
return a [x] < a [y];
}
可以用lambda表达式
保证sort的下标不变可以用stl的自带函数stable_sort