서로 다른 수와 쿼리 1 (백준 14897)

안녕하세요. 오늘은 서로다른수의 개수를 세어볼 거예요.

문제

https://www.acmicpc.net/problem/14897

아이디어

모스 알고리즘을 쓰면 됩니다.
수의 개수를 세려면 배열이 필요하므로 수도 압축을 해야합니다.

소스코드

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

int sqrt_N;
struct Query {
    int i, j, index;
};
bool comp(Query A, Query B)
{
    if (A.i / sqrt_N == B.i / sqrt_N) return A.j < B.j;
    return A.i < B.i;
}

vector <int> v;
int cal(int x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

int num[1010101] = { 0 };
int n, i, m, arr[1010101] = { 0 }, cnt = 0, Answer[1010101] = { 0 }, l, r;
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    vector <Query> vec;
    Query temp;

    cin >> n;
    sqrt_N = sqrt(n);
    for (i = 1; i <= n; i++)
    {
        cin >> arr[i];
        v.push_back(arr[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (i = 1; i <= n; i++) arr[i] = cal(arr[i]);

    cin >> m;
    for (i = 0; i < m; i++)
    {
        cin >> l >> r;
        temp.i = l;
        temp.j = r;
        temp.index = i;
        vec.push_back(temp);
    }
    sort(vec.begin(), vec.end(), comp);
    for (i = 0; i < m; i++)
    {
        if (i == 0)
        {
            l = vec[i].i;
            r = vec[i].i;
            num[arr[l]] = 1;
            cnt = 1;
        }

        while (l < vec[i].i)
        {
            num[arr[l]]--;
            if (num[arr[l]] == 0) cnt--;
            l++;
        }
        while (l > vec[i].i)
        {
            l--;
            num[arr[l]]++;
            if (num[arr[l]] == 1) cnt++;
        }
        while (r < vec[i].j)
        {
            r++;
            num[arr[r]]++;
            if (num[arr[r]] == 1) cnt++;
        }
        while (r > vec[i].j)
        {
            num[arr[r]]--;
            if (num[arr[r]] == 0) cnt--;
            r--;
        }
        Answer[vec[i].index] = cnt;
    }
    for (i = 0; i < m; i++)
        cout << Answer[i] << "\n";
}

감사합니다.