BOJ 2912 - 백설공주와 난쟁이 링크
(2023.06.28 기준 P2)

문제

백설공주와 난쟁이 N명이 있다.
난쟁이들은 모두 줄을 서 있고, 모자를 쓰고 있으며 모자의 색상은 총 C가지가 있다.

백설공주는 난쟁이들을 찍은 사진 M개가 있는데, 각 사진은 'A B'로 주어지며 A번째 난쟁이부터 B번째 난쟁이까지 찍혀있다는 뜻이다.
사진에 난쟁이가 K명 찍혀있고, K/2보다 많은 난쟁이의 모자 색이 같다면 예쁜 사진일 때, 각 사진마다 예쁜 사진인지 아닌지를 출력

알고리즘

수열의 값 변경이 일어나지 않으므로 효과적인 구간 쿼리 처리를 위해 제곱근 분할법을 이용한 mo's를 사용하자.

풀이

mo's는 대략적으로 설명하자면, 겹치는 구간 쿼리마다 겹치는 구간을 최대한 재사용해서 시간복잡도를 줄이는 것이다.
[2, 3] 구간, [1, 4] 구간 쿼리가 있다면, 당연히 [2, 3] 구간 쿼리를 처리 후, 1,4 부분만 따로 구해주면 [1, 4] 구간 쿼리를 효과적으로 처리가 가능하다.

이를 √N개의 구간으로 분할하여 관리하는 제곱근 분할법을 쿼리에 적용하여 오프라인 쿼리로 처리하면 각 구간 쿼리마다 양 끝점이 움직이는 횟수는 최대 √N번이다.
자세한 설명은 구글링하자. 많은 블로그에 자세한 설명이 적혀 있다.

이 문제는 따로 버킷을 관리해 줄 필요는 없다.
쿼리를 제곱근 분할법으로 정렬하여 쿼리 순서대로 현재 범위를 좁히고 늘리면서 모자의 색상을 카운트해주기만 하자. 그리고 쿼리 당 범위 조절이 끝날 때마다 K/2보다 넘는 모자 색이 있는지 모든 모자에 대해 검사하면 된다. 이는 쿼리 최대 10,000이고 모자의 색상도 최대 10,000이어서 충분히 가능하다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 10000;

int C, k, ct[MAX + 1], answer[MAX];

struct Query{ // 쿼리 구조체
    int A, B, idx;

    bool operator < (const Query &that) const{
        if (this->A / k == that.A / k)
            return this->B < that.B;
        return this->A / k < that.A / k;
    }
};

// 절반보다 많은 수의 모자 색이 있는지 확인
int check(int half){
    for (int i = 1; i <= C; i++)
        if (ct[i] > half) return i;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N >> C;
    int arr[N]; for (int i = 0; i < N; i++) cin >> arr[i];

    int M; cin >> M;
    vector<Query> queries;
    for (int i = 0, A, B; i < M; i++){
        cin >> A >> B;
        queries.push_back({--A, --B, i});
    }

    // 제곱근 분할
    k = sqrt(N);
    sort(queries.begin(), queries.end());

    // 첫번째 쿼리의 범위부터 시작
    auto [L, R, idx] = queries[0];
    fill(ct + 1, ct + C + 1, 0);
    for (int i = L; i <= R; i++) ct[arr[i]]++;

    answer[idx] = check((R - L + 1) / 2);

    for (int i = 1; i < M; i++){
        auto [A, B, idx] = queries[i];
        while (L < A) // 왼쪽 범위 좁히기
            ct[arr[L++]]--;
        while (A < L) // 왼쪽 범위 늘리기
            ct[arr[--L]]++;
        while (B < R) // 오른쪽 범위 좁히기
            ct[arr[R--]]--;
        while (R < B) // 오른쪽 범위 늘리기
            ct[arr[++R]]++;
        answer[idx] = check((R - L + 1) / 2);
    }

    for (int i = 0; i < M; i++){
        if (answer[i]) cout << "yes " << answer[i] << '\n';
        else cout << "no" << '\n';
    }
}

• Python (PyPy3)

import sys; input = sys.stdin.readline

# 절반보다 많은 수의 모자 색이 있는지 확인
def check(half):
    for i in range(1, C + 1):
        if ct[i] > half:
            return i
    return 0

N, C = map(int, input().split())
arr = list(map(int, input().split()))

M = int(input())
queries = []
for i in range(M):
    A, B = map(int, input().split())
    queries.append((A - 1, B - 1, i))

# 제곱근 분할
k = int(N ** 0.5)
queries.sort(key = lambda x: (x[0] // k, x[1]))

# 첫번째 쿼리의 범위부터 시작
L, R, idx = queries[0]
ct = [0] * (C + 1)
for i in range(L, R + 1):
    ct[arr[i]] += 1

answer = [0] * M
answer[idx] = check((R - L + 1) / 2)

for A, B, idx in queries[1:]:
    while L < A: # 왼쪽 범위 좁히기
        ct[arr[L]] -= 1
        L += 1
    while A < L: # 왼쪽 범위 늘리기
        L -= 1
        ct[arr[L]] += 1
    while B < R: # 오른쪽 범위 좁히기
        ct[arr[R]] -= 1
        R -= 1
    while R < B: # 오른쪽 범위 늘리기
        R += 1
        ct[arr[R]] += 1
    answer[idx] = check((R - L + 1) / 2)

for i in range(M):
    if answer[i]:
        print('yes %d' % answer[i])
    else:
        print('no')