[Algorithm] cpp 백준 2912번: 백설공주와 난쟁이

문제

링크: https://www.acmicpc.net/problem/2912
요약: 길이 \(N\)의 모자 색 배열에서 구간 \([A,B]\)에 절반을 초과해 등장하는 색이 있는지, 있다면 그 색을 \(M\)개의 질의에 대해 판단합니다.
제한: \(N \le 3\times10^5\), \(C \le 10^4\), \(M \le 10^4\), 시간 1초

입력/출력

1
2
3
4
5
6
7
8
9
입력
N C
colors[1..N]
M
A B (M줄)

출력
각 질의에 대해, 다수색이 없으면 "no",
있으면 "yes X" (X는 다수색 번호)

접근 개요

핵심 아이디어: 구간의 다수 원소(majority)는 Boyer–Moore 다수결의 법칙처럼, 후보와 카운트를 병합해도 후보가 유지됩니다. 이를 세그먼트 트리로 일반화하면, 구간 병합으로 후보를 빠르게 구할 수 있습니다.
검증 단계: 후보가 실제로 절반을 초과하는지 확인하려면 색상별로 등장 위치를 저장해 두고, \([A,B]\)에서의 빈도를 이분탐색(lower/upper_bound)으로 계산합니다.
복잡도: 빌드 \(O(N)\), 질의당 후보 추출 \(O(\log N)\) + 검증 \(O(\log N)\) → 전체 \(O((N+M)\log N)\).

Mermaid로 보는 흐름

flowchart TD
    Q[Query [A,B]] --> ST[Segment Tree Query]
    ST --> Cand[Candidate (color,count)]
    Cand --> Verify[positions[color]로 빈도 이분탐색]
    Verify --> Decision{cnt > len/2?}
    Decision -- Yes --> YesOut["yes color"]
    Decision -- No --> NoOut["no"]

알고리즘 설계

세그먼트 트리 노드: (color, count)
- 두 노드 병합:
  - 같으면 (color, countL+countR)
  - 다르면 더 큰 쪽 카운트에서 작은 쪽을 상쇄하여 후보 유지
  - 공집합 대용 color=-1
색상별 등장 위치 벡터 positions[color]에 인덱스들을 정렬 저장
질의 처리:
1. 세그트리에서 후보색 cand.color 구하기
2. positions[cand.color]에서 \([A,B]\) 빈도를 upper_bound - lower_bound로 계산
3. cnt > (B-A+1)/2면 다수색

정당성 근거

Boyer–Moore의 상쇄 법칙: 서로 다른 원소를 짝지어 제거해도 다수 원소(절반 초과)는 남습니다. 세그먼트 트리 병합은 이 상쇄를 구간 단위로 일반화하여 후보를 보존합니다.
후보의 실제 다수 여부는 위치 배열을 통한 정확한 빈도 계산으로 최종 검증됩니다.

복잡도

시간: 빌드 \(O(N)\), 질의당 \(O(\log N)\)
공간: 세그먼트 트리 \(O(N)\) + 위치 벡터 총합 \(O(N)\)

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Node { int color; int count; };

Node mergeNode(const Node &L, const Node &R) {
    if (L.color == -1) return R;
    if (R.color == -1) return L;
    if (L.color == R.color) return {L.color, L.count + R.count};
    if (L.count > R.count) return {L.color, L.count - R.count};
    return {R.color, R.count - L.count};
}

int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
    int N,C; if(!(cin>>N>>C)) return 0;
    vector<int> a(N+1);
    vector<vector<int>> pos(C+1);
    for(int i=1;i<=N;++i){cin>>a[i]; if(1<=a[i] && a[i]<=C) pos[a[i]].push_back(i);}    

    vector<Node> seg(4*N+4, {-1,0});
    function<void(int,int,int)> build = [&](int idx,int l,int r){
        if(l==r){ seg[idx]={a[l],1}; return; }
        int m=(l+r)>>1; build(idx<<1,l,m); build(idx<<1|1,m+1,r);
        seg[idx]=mergeNode(seg[idx<<1],seg[idx<<1|1]);
    };
    function<Node(int,int,int,int,int)> query = [&](int idx,int l,int r,int ql,int qr)->Node{
        if(qr<l||r<ql) return Node{-1,0};
        if(ql<=l && r<=qr) return seg[idx];
        int m=(l+r)>>1; Node L=query(idx<<1,l,m,ql,qr), R=query(idx<<1|1,m+1,r,ql,qr);
        return mergeNode(L,R);
    };
    auto countInRange = [&](const vector<int>& v, int L, int R){
        auto itL=lower_bound(v.begin(),v.end(),L);
        auto itR=upper_bound(v.begin(),v.end(),R);
        return (int)(itR-itL);
    };

    build(1,1,N);
    int M; cin>>M;
    while(M--){
        int A,B; cin>>A>>B; if(A>B) swap(A,B);
        Node cand=query(1,1,N,A,B);
        int color=cand.color; int len=B-A+1; int cnt=0;
        if(color!=-1 && 1<=color && color<=C) cnt=countInRange(pos[color],A,B);
        if(cnt>len/2) cout<<"yes "<<color<<'\n'; else cout<<"no\n";
    }
    return 0; }