[BOJ/Platinum 1] 백준 13548 수열과 쿼리 6(C++)

문제 링크

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

13548번: 수열과 쿼리 6

 

문제

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

• i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다.

입력

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

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

2
1
2

알고리즘 분류

• 평행 분할

풀이

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

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

이제 각 쿼리문마다 해당하는 정답을 구한다. 먼저 2가지를 기록해놓아야 한다. 첫 번째는 숫자의 등장 횟수 Count이고, 두 번째는 X번 등장한 숫자의 개수 Count_Count이다. Count_Count[Count[X]]가 1 이상인 Count[X] 중에서 최대인 값이 쿼리문의 구간 내에 가장 많이 등장하는 숫자의 등장 횟수가 된다.

첫 번째 쿼리문에 해당하는 구간을 전부 탐색하면서 숫자가 등장하면, Count_Count[Count[X]]를 감소시킨 후 Count[X]를 1 증가시키고 Count_Count[Count[X]]를 1 증가시킨다. 그리고 값과 Count_Count[Count[X]]를 비교해 최댓값을 갱신한다.

구간을 전부 탐색한 후 나오는 값이 현재, 즉 첫 번째 쿼리문의 Index번째에 해당하는 정답, 그러니까 현재 구간에서 가장 많이 등장하는 수의 등장 횟수가 된다.

이제부터는 M-1개의 쿼리문에 해당하는 정답을 전부 구한다. 현재 지정된 구간의 시작과 끝을 현재 쿼리문에 해당하는 구간으로 맞춰가면서 원소를 추가하거나 제외시킨다. 원소를 제외시킬 때에는 Count_Count[Count[X]]를 1 감소시키고, Count_Count[Count[X]]가 0이 되었다면 현재 값이 Count[X]인지 확인하고 일치한다면 값을 1 감소시킨다. 그리고 Count[X]를 1 감소시키고 Count_Count[Count[X]]를 증가시킨다.

작업이 모두 끝나면 나오는 값이 현재 쿼리문의 Index번째에 해당하는 정답이 되고, 다음 쿼리문으로 넘어간다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MAX 100001
#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;
int Count[MAX], Count_Count[MAX];
int Answer[MAX];

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);
    Left = Query[0].Left;
    Right = Query[0].Right;
    for (int i = Left; i <= Right; i++) {
        int Now = A[i];
        Count_Count[Count[Now]]--;
        Count[Now]++;
        Value = max(Value, Count[Now]);
        Count_Count[Count[Now]]++;
    }
    Answer[Query[0].Index] = Value;
    for (int i = 1; i < M; i++) {
        while (Query[i].Left < Left) {
            Left--;
            int Now = A[Left];
            Count_Count[Count[Now]]--;
            Count[Now]++;
            Value = max(Value, Count[Now]);
            Count_Count[Count[Now]]++;
        };

        while (Query[i].Left > Left) {
            int Now = A[Left];
            Count_Count[Count[Now]]--;
            if ((Count_Count[Count[Now]] == 0) && (Value == Count[Now])) {
                Value--;
            }
            Count[Now]--;
            Count_Count[Count[Now]]++;
            Left++;
        };

        while (Query[i].Right > Right) {
            Right++;
            int Now = A[Right];
            Count_Count[Count[Now]]--;
            Count[Now]++;
            Value = max(Value, Count[Now]);
            Count_Count[Count[Now]]++;
        };

        while (Query[i].Right < Right) {
            int Now = A[Right];
            Count_Count[Count[Now]]--;
            if ((Count_Count[Count[Now]] == 0) && (Value == Count[Now])) {
                Value--;
            }
            Count[Now]--;
            Count_Count[Count[Now]]++;
            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;
}