이 문제는 주어진 배열의 특정 구간에 존재하는 서로 다른 숫자의 개수를 구하는 것을 목표로 합니다. 이를 해결하기 위해 펜윅 트리(Fenwick Tree)와 오프라인 쿼리 처리 기법을 활용합니다.

펜윅 트리를 사용할 때 핵심은 각 위치에서 해당 요소가 마지막으로 등장한 위치를 추적하고, 새로운 위치에서 등장할 경우 이전 위치의 값을 제거하고 현재 위치를 갱신하는 것입니다.

그러나 단순히 순차적으로 처리하면 중복된 요소가 여러 번 카운트되는 문제가 발생할 수 있습니다. 예를 들어, 동일한 값이 여러 위치에 분포되어 있고, 쿼리 범위가 점점 줄어드는 경우 잘못된 결과가 나올 수 있습니다. 이러한 상황을 방지하기 위해 오프라인 쿼리 방식을 적용합니다.

오프라인 처리란 모든 쿼리를 미리 입력받아 특정 기준(예: 구간의 끝점)에 따라 정렬한 후 순차적으로 처리하고, 최종적으로 원래 순서로 결과를 재정렬하여 출력하는 방식입니다. 이를 통해 중복 처리 문제를 효과적으로 회피할 수 있습니다.

구현 방법

쿼리 정보를 저장하는 구조체를 정의하고, 두 가지 기준으로 정렬할 수 있는 비교 함수를 작성합니다:

struct Query {
    int left, right, result, index;
} queries[MAX];

bool compareByRight(Query a, Query b) {
    return a.right < b.right;
}

bool compareById(Query a, Query b) {
    return a.index < b.index;
}

메인 로직에서는 먼저 모든 쿼리를 입력받고, 구간의 끝점을 기준으로 정렬합니다. 이후 배열을 순회하면서 펜윅 트리에 값을 업데이트하고, 현재 위치가 쿼리의 끝점과 일치할 때 해당 구간의 결과를 계산합니다.

완성 코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX = 500005;
int tree[MAX], lastPos[1000005], arr[MAX];
int n, m;

inline int lowbit(int x) {
    return x & (-x);
}

void update(int pos, int delta) {
    for (int i = pos; i <= n; i += lowbit(i))
        tree[i] += delta;
}

int prefixSum(int pos) {
    int sum = 0;
    for (int i = pos; i > 0; i -= lowbit(i))
        sum += tree[i];
    return sum;
}

struct Query {
    int left, right, answer, idx;
} q[MAX];

bool sortByRight(Query a, Query b) {
    return a.right < b.right;
}

bool sortById(Query a, Query b) {
    return a.idx < b.idx;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> q[i].left >> q[i].right;
        q[i].idx = i;
    }

    sort(q + 1, q + m + 1, sortByRight);

    int ptr = 1;
    for (int i = 1; i <= n; i++) {
        if (lastPos[arr[i]]) {
            update(lastPos[arr[i]], -1);
        }
        update(i, 1);
        lastPos[arr[i]] = i;

        while (ptr <= m && q[ptr].right == i) {
            q[ptr].answer = prefixSum(q[ptr].right) - prefixSum(q[ptr].left - 1);
            ptr++;
        }
    }

    sort(q + 1, q + m + 1, sortById);
    for (int i = 1; i <= m; i++)
        cout << q[i].answer << "\n";

    return 0;
}