与$dalao$们的想法相同,下面的代码可能更好阅读一点。
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<unordered_map>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 200000 + 10;
typedef pair<int, int> PII;
PII arr[MAXN];
unordered_map<int, PII> book;
int main(void){
int N;
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d", &arr[i].first);
arr[i].second = i;
}
sort(arr, arr + N);
for(int i=0; i<N; i++){
if(book.find(arr[i].first) == book.end()) book[ arr[i].first ] = {INF, 0};
book[ arr[i].first ].first = min( arr[i].second, book[ arr[i].first ].first );
book[ arr[i].first ].second = max( arr[i].second, book[ arr[i].first ].second );
}
int cnt = 0, lastNum = INF, state = 1;
int uniqueNum = -1;
for(int i=0; i<N; i++){
PII p = book[arr[i].first];
if(uniqueNum == arr[i].first) continue;
else uniqueNum = arr[i].first;
if(state){
if(lastNum > p.second){
lastNum = p.first;
}else{
state = !state;
lastNum = p.second;
cnt ++;
}
}else{
if(lastNum < p.first){
lastNum = p.second;
}else{
state = !state;
lastNum = p.first;
}
}
}
if(state) cnt ++;
printf("%d\n", cnt);
return 0;
}