팬미팅 (JUNGOL 5768)

https://jungol.co.kr/problem/5768

---

아이디어

모든 인덱스 i에 대해서 idx[i]를 (i와 같은 수가 있고 i보다 오른쪽에 있는 가장 작은 인덱스)라고 정의합시다. 그러면 모든 i에 대해서 구간 [i+1,idx[i]-1]에 존재하는 서로다른 수의 개수를 모두 더해주면 됩니다. 이는 mo's로 해결해줄 수 있습니다.

---

소스코드

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll sqrtN;
bool cmp(pair <ll,ll> A,pair <ll,ll> B)
{
    if (A.first/sqrtN!=B.first/sqrtN) return A.first<B.first;
    return A.second<B.second;
}

ll Last[202020]={0};
ll Count[202020]={0};
ll arr[202020]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N;

    cin>>N;
    sqrtN=sqrt(N);

    vector <pair <ll,ll> > Query;
    for (ll i=1;i<=N;i++)
    {
        ll x;
        cin>>x;
        arr[i]=x;

        Query.push_back({Last[x]+1,i-1});
        Last[x]=i;
    }

    sort (Query.begin(),Query.end(),cmp);

    ll res=0,s=1,e=0,cnt=0;
    for (auto [Left,Right]:Query)
    {
        while (Left<s)
        {
            s--;
            if (Count[arr[s]]==0) cnt++;
            Count[arr[s]]++;
        }
        while (e<Right)
        {
            e++;
            if (Count[arr[e]]==0) cnt++;
            Count[arr[e]]++;
        }
        while (Left>s)
        {
            if (Count[arr[s]]==1) cnt--;
            Count[arr[s]]--;
            s++;
        }
        while (e>Right)
        {
            if (Count[arr[e]]==1) cnt--;
            Count[arr[e]]--;
            e--;
        }

        res+=cnt;
    }

    cout<<res;
}