[BOJ/Platinum 2] 백준 13547 수열과 쿼리 5(C++)

문제 링크

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

13547번: 수열과 쿼리 5

 

 

문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000)

셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

넷째 줄부터 M개의 줄에는 쿼리 i, j가 한 줄에 하나씩 주어진다. (1 ≤ i ≤ j ≤ N)

출력

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

예제 입력 1

5
1 1 2 1 3
3
1 5
2 4
3 5

예제 출력 1

3
2
3

알고리즘 분류

• 평행 분할

풀이

길이가 10만인 수열의 특정 구간 내에서 서로 다른 수의 개수를 구하는 작업을 2초 안에 10만번이나 수행하기에는 무리가 있다.

다행히 수열의 원소를 갱신하는 쿼리문이 존재하지 않고, 모든 쿼리문을 미리 알고 있기 때문에 각 쿼리문에 해당하는 정답을 전부 구해둔다.

길이가 N인 수열의 원소를 k(√ N)개로 이루어진 그룹으로 나누어 데이터를 관리하는 모스 알고리즘을 사용한다.

우선 M개의 쿼리문을 구간의 시작과 끝, 그리고 쿼리문 자체의 Index 변수를 갖는 구조체로서 벡터에 저장하고, 구간의 시작 Index를 √ N로 나눈 값에 따라 오름차순으로 정렬한다. 만약 그 값이 같은 경우에는 구간의 끝 Index에 따라 오름차순으로 정렬한다.

이제 각 쿼리문마다 해당하는 정답을 구한다. 먼저 첫 번째 쿼리문에 해당하는 구간을 전부 탐색하면서 등장하는 숫자의 개수를 센다. 만약 처음 등장하는 숫자라면 값을 증가시킨다.

구간을 전부 탐색하고 나온 값이 현재, 즉 첫 번째 쿼리문의 Index번째에 해당하는 정답이 된다.

이제부터는 M-1개의 쿼리문에 해당하는 정답을 전부 구한다. 현재 지정된 구간의 시작과 끝을 현재 쿼리문에 해당하는 구간으로 맞춰가면서 원소를 추가하거나 제외시킨다. 원소를 제외시킬 때에는 해당 원소의 개수를 감소시키고, 개수가 0이 되면 값을 감소시킨다. 작업이 모두 끝나면 나오는 값이 현재 쿼리문의 Index번째에 해당하는 정답이 되고, 다음 쿼리문으로 넘어간다.

이렇게 M개의 쿼리문에 해당하는 정답을 모두 구하고, 마지막으로 M개의 정답을 모두 출력하면 O(N√ N)만큼의 시간복잡도를 가지고 문제를 해결할 수 있어 2초 안에 충분히 길이가 10만인 수열의 특정 구간 내에서 서로 다른 수의 개수를 구하는 10만개의 쿼리문을 수행할 수 있다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MAX 1000001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct QUERY {
    int Left, Right, Index;
};

int N, M, S, I, J;
int A[MAX];
vector<QUERY> Query;
int Value, Left, Right;
vector<int> Answer, Count;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> I >> J;
        Query.push_back({ I - 1,J - 1,i });
    }
}

bool Comp(QUERY A, QUERY B) {
    if (A.Left / S != B.Left / S) {
        return (A.Left / S < B.Left / S);
    }
    return (A.Right < B.Right);
}

void settings() {
    S = sqrt(N);
    sort(Query.begin(), Query.end(), Comp);
    Answer.resize(M);
    Count.resize(MAX);
    Left = Query[0].Left;
    Right = Query[0].Right;
    for (int i = Left; i <= Right; i++) {
        if (Count[A[i]] == 0) {
            Value++;
        }
        Count[A[i]]++;
    }
    Answer[Query[0].Index] = Value;
    for (int i = 1; i < M; i++) {
        int NowL = Query[i].Left;
        int NowR = Query[i].Right;

        while (NowL < Left) {
            Left--;
            if (Count[A[Left]] == 0) {
                Value++;
            }
            Count[A[Left]]++;
        };

        while (NowL > Left) {
            Count[A[Left]]--;
            if (Count[A[Left]] == 0) {
                Value--;
            }
            Left++;
        };

        while (NowR > Right) {
            Right++;
            if (Count[A[Right]] == 0) {
                Value++;
            }
            Count[A[Right]]++;
        };

        while (NowR < Right) {
            Count[A[Right]]--;
            if (Count[A[Right]] == 0) {
                Value--;
            }
            Right--;
        };

        Answer[Query[i].Index] = Value;
    }
}

void find_Answer() {
    for (int i = 0; i < M; i++) {
        cout << Answer[i] << "\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}