[BOJ/Platinum 1] 백준 14413 Poklon(C++)

문제 링크

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

14413번: Poklon

 

문제

Little Mirko is a very simple man. Mirko’s friend Darko has given him an array of N natural integers and asked him Q queries about the array that Mirko must answer.

Each query consists of two integers, the positions of the left and right end of an interval in the array. The answer to the query is the number of different values that appear exactly twice in the given interval.

입력

The first line of input contains the integers N and Q (1 ≤ N, Q ≤ 500 000).

The second line of input contains N natural integers less than 1 000 000 000, the elements of the array.

Each of the following Q lines contains two integers, L and R (1 ≤ L ≤ R ≤ N), from the task.

출력

The output must consist of Q lines, each line containing the answer to a query, respectively.

예제 입력 1

5 1
1 2 1 1 1
1 3

예제 출력 1

1

예제 입력 2

5 2
1 1 1 1 1
2 4
2 3

예제 출력 2

0
1

예제 입력 3

5 2
1 1 2 2 3
1 1
1 5

예제 출력 3

0
2

알고리즘 분류

• 평행 분할

풀이

길이가 50만인 배열의 특정 구간 내에 등장하는 정수의 개수를 구하는 작업을 5초 안에 50만번이나 수행하기에는 무리가 있어 모스 알고리즘을 통해 해결한다.

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

이제 각 쿼리문마다 해당하는 정답을 구한다. 먼저 첫 번째 쿼리문에 해당하는 구간을 전부 탐색하면서 등장하는 정수의 개수를 증가시킨다. 이 때 이 정수의 개수가 2가 된다면 값을 증가시키고, 3이 된다면 값을 1 감소시킨다.

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

이제부터는 M-1개의 쿼리문에 해당하는 정답을 전부 구한다. 현재 지정된 구간의 시작과 끝을 현재 쿼리문에 해당하는 구간으로 맞춰가면서 원소를 추가하거나 제외시킨다. 원소를 제외할 때에는 정수의 개수가 2가 된다면 값을 증가시키고, 1이 된다면 값을 1 감소시킨다.

코드

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

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

int N, Q, S, L, R;
int A[MAX];
unordered_map<int, int> UM;
vector<QUERY> Query;
int Left, Right, Value;
int Count[MAX], Count_Count[MAX];
int Answer[MAX];


void input() {
    cin >> N >> Q;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (UM.find(A[i]) == UM.end()) {
            UM.insert(make_pair(A[i], i));
        }
    }
    for (int i = 0; i < Q; i++) {
        cin >> L >> R;
        Query.push_back({ L - 1,R - 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);
    Left = Query[0].Left;
    Right = Query[0].Right;
    for (int i = Left; i <= Right; i++) {
        int Now = A[i];
        Count[Now]++;
        if (Count[Now] == 2) {
            Value++;
        }
        else if (Count[Now] == 3) {
            Value--;
        }
    }
    Answer[Query[0].Index] = Value;
    for (int i = 1; i < Q; i++) {
        while (Query[i].Left < Left) {
            Left--;
            int Now = A[Left];
            Count[Now]++;
            if (Count[Now] == 2) {
                Value++;
            }
            else if (Count[Now] == 3) {
                Value--;
            }
        };

        while (Query[i].Left > Left) {
            int Now = A[Left];
            Count[Now]--;
            if (Count[Now] == 2) {
                Value++;
            }
            else if (Count[Now] == 1) {
                Value--;
            }
            Left++;
        };

        while (Query[i].Right > Right) {
            Right++;
            int Now = A[Right];
            Count[Now]++;
            if (Count[Now] == 2) {
                Value++;
            }
            else if (Count[Now] == 3) {
                Value--;
            }
        };

        while (Query[i].Right < Right) {
            int Now = A[Right];
            Count[Now]--;
            if (Count[Now] == 2) {
                Value++;
            }
            else if (Count[Now] == 1) {
                Value--;
            }
            Right--;
        };

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

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

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

    return 0;
}