https://www.acmicpc.net/problem/2912
2912번: 백설공주와 난쟁이
첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000) 둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다. 셋째 줄에는 사진
www.acmicpc.net
N명의 난쟁이가 모자를 쓰고 줄을 서고 있습니다.
구간 l ~ r에 존재하는 모자의 색상의 갯수를 종류별로 파악하여 어떤 모자가 절반보다 많이 있다면 yes와 색의 번호를 출력합니다.
이 문제에 업데이트가 없으므로 오프라인 쿼리가 가능하며, 구간을 효율적으로 움직이기 위해 Mo's 알고리즘을 사용합니다.
먼저 구간을 sqrt(N)으로 나누어 l / sqrt(N)을 기준으로 오름차순 정렬합니다.
l의 구간이 같다면 r을 기준으로 오름차순 정렬합니다.
그 다음 정렬된 쿼리를 하나씩 처리합니다.
구간을 이동하면서 색에 대한 카운팅을 진행합니다.
해당 구간에 대한 카운팅이 끝났으면 어떤 색이 절반보다 많이 차지하는지 찾습니다. (없다면 -1입니다.)
그 다음 구간을 갱신합니다.
M개의 쿼리를 모두 처리한 다음 한꺼번에 출력합니다.
|
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <iostream>
#include <algorithm>
#include <cmath>
#define MAX 300001
#define MAXQ 10001
using namespace std;
typedef struct Point {
int l, r, idx;
}Point;
Point q[MAXQ];
int list[MAX], ans[MAXQ], cnt[MAXQ];
int N, C, M, sqrtN;
bool cmp(Point a, Point b) {
int x = a.l / sqrtN;
int y = b.l / sqrtN;
if (x == y) return a.r < b.r;
else return x < y;
}
void solve(int idx, int k) {
for (int i = 1; i <= C; i++) {
if (cnt[i] > k / 2) {
ans[idx] = i;
return;
}
}
ans[idx] = -1;
}
void func() {
int l = q[1].l;
int r = q[1].r;
for (int i = l; i <= r; i++) {
cnt[list[i]]++;
}
solve(q[1].idx, r - l + 1);
for (int i = 2; i <= M; i++) {
int nl = q[i].l;
int nr = q[i].r;
int idx = q[i].idx;
for (int j = l; j < nl; j++) {
cnt[list[j]]--;
}
for (int j = l - 1; j >= nl; j--) {
cnt[list[j]]++;
}
for (int j = r; j > nr; j--) {
cnt[list[j]]--;
}
for (int j = r + 1; j <= nr; j++) {
cnt[list[j]]++;
}
solve(idx, nr - nl + 1);
l = nl;
r = nr;
}
for (int i = 1; i <= M; i++) {
if (ans[i] == -1) cout << "no\n";
else cout << "yes " << ans[i] << '\n';
}
}
void input() {
cin >> N >> C;
for (int i = 1; i <= N; i++) {
cin >> list[i];
}
sqrtN = sqrt(N);
cin >> M;
for (int i = 1; i <= M; i++) {
cin >> q[i].l >> q[i].r;
q[i].idx = i;
}
sort(q + 1, q + 1 + M, cmp);
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Mo's' 카테고리의 다른 글
| boj 12999 화려한 마을3 (0) | 2022.09.07 |
|---|