R495(Div.2) C. Sonya and Robots

문제를 요약하자면

예를 들어 배열 [1,5,4,1,3]이 있을 때 

우리는 a가 먼저 나오고 b가 나중에 나오는 순서쌍 (a,b)에 수를 찾으면 된다

무슨 말이냐면 순서쌍 (1,3)은 1이 앞에 3이 뒤에 이므로 가능하다

근데 (3,1) 같은 경우는 3보다 1이 앞에 있으므로 교차하게 되어 불가능하다

즉 맨 앞과 맨 뒤에서 출발했을 때 교차하지 않는 순서쌍의 수를 찾으면 된다!

+ 중복불가

문제는 set과 map을 사용해 풀었다

map에는 각 숫자의 수를 저장했고 set은 내가 갈 수 있는 수를 의미한다

그럼 맨 앞부터 수를 보면서 set의 size만큼을 더해주면 된다

이 때 내가 볼 때마다 map에서 수를 1씩 줄여준다 

그리고 0이 되면 set에서 사라지게 해준다

추가로 used배열을 사용했는데 used는 이미 본 숫자라면 ans에 숫자를 더하지 않게 하기 위해 사용했다. 숫자는 안 더해도 map에서 수는 빼준다

설명을 대충썼더니 이상한거같다 ㅎㅎㅎㅎ

어쨌든 내 오른쪽만 계속 보면 된다!

소스코드

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 5;
int n, arr[MAXN], cnt[MAXN];
bool used[MAXN];
set<int >s;
map<int, int> mp;
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        scanf(" %d", &arr[i]);
        cnt[arr[i]]++;
        mp[arr[i]]++;
        s.insert(arr[i]);
    }
 
    ll ans = 0;
    for (int i = 0; i < n-1; i++) {
        if (!s.count(arr[i])) continue;
        bool c = used[arr[i]];
        used[arr[i]] = true;
        mp[arr[i]]--;
        if (mp[arr[i]] == 0) s.erase(arr[i]);
        if (!c)ans += (ll)s.size();
    }
    printf("%lld\n", ans);
}