https://www.acmicpc.net/problem/12999
12999번: 화려한 마을3
첫 번째 줄에 N, Q (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 수와 민호가 궁금해 하는 특정 구간의 수이다. 두 번째 줄에는 1번 집부터 N번 집까
www.acmicpc.net
구간 l ~ r에 존재하는 집에 칠해진 페인트의 밝기들 중 가장 많은 것의 갯수를 출력합니다.
즉, [l, r] 구간에 {1, 1, 1, 2, 2}가 있다면 1이 3개, 2가 2개이므로 3을 출력합니다.
이 문제에서 사용할 배열은
- q: 쿼리 정보를 저장하는 배열
- list: 페인트의 밝기를 저장하는 배열
- ans: 답을 저장하는 배열
- cnt: 특정 밝기의 등장 횟수
- cntCnt: 특정 밝기의 등장 횟수의 등장 횟수
여기서 cntCnt는 1이 3번, 2가 3번 등장했다면 cntCnt[3] = 2 이렇게 되는 방식입니다.
페인트의 밝기는 -100000 ~ 100000이므로 100000을 미리 더해주도록 합시다. 그래서 cnt 배열의 크기는 *2가 됩니다.
페인트의 밝기는 업데이트가 되지 않으므로 오프라인 쿼리 사용이 가능합니다.
따라서 쿼리 정보를 한 번에 받아서 배열 q에 저장합니다.
출력은 입력 순으로 해야하니 인덱스도 함께 저장해야 합니다.
그 다음, 투 포인터 비슷하게 l ~ r 구간을 하나하나 확인하여 갯수 카운팅을 진행합니다.
하지만 범위가 1 ~ 5 -> 9 ~ 10 -> 1 ~ 2 이런식으로 된다면 포인터가 이동하는데 많은 시간이 걸릴 것입니다.
포인터를 효율적으로 이동시키기 위해 Mo's 알고리즘을 사용합니다.
Mo's 알고리즘으로 구간을 sqrt(N)으로 나누어서 최대한 같은 그룹 내에서 이동할 수 있도록 하여 움직임을 최소화할 수 있습니다.
따라서 l / sqrt(N)을 기준으로 오름차순으로 정렬하며, 같다면 r 기준으로 오름차순으로 정렬합니다.
이제 정렬된 쿼리를 하나씩 처리하면 됩니다.
구간을 이동시키면서 수를 제거하고, 추가합니다.
수를 제거하는 과정에서는 먼저 해당 수가 등장한 횟수인 cntCnt를 하나 빼야합니다.
1이 3번 등장해서 cntCnt[3] = 1이 되었는데, 구간을 이동시키니 1이 제거돼야 하는 상황이라면 1이 2번 등장하는 것으로 바뀌게 됩니다.
따라서 cntCnt[3]에서 1을 빼고, cntCnt[2]에서 1을 더해야 합니다.
이 때, 만약 cntCnt[3]이 0이 되었고, 그게 현재 최대 등장 횟수 ret이었다면 ret 또한 1을 빼야합니다.
수를 추가하는 과정에서는 해당 수가 처음 등장하는 수가 아니라면 cntCnt를 하나 빼줍니다.
1이 3번 등장해서 cntCnt[3] = 1이 되었고, 구간을 이동시켜서 1이 추가되는 상황이라면 1이 4번 등장하는 것으로 바뀌게 됩니다.
따라서 cntCnt[3]에서 1을 빼고, cntCnt[4]에서 1을 더해야 합니다.
물론, 1이 등장한 적 없다가 추가되는 상황이면 cntCnt를 빼지 않아야 합니다.
그리고 등장 횟수를 추가하는 과정이므로 최대 등장 횟수 ret을 계속 갱신합니다.
위 두 가지 작업이 완료되었다면 구간을 갱신하고, 쿼리의 인덱스에 맞게 정답을 넣어줍니다.
쿼리가 입력 순으로 정렬되어 있지 않으므로 출력은 마지막에 한꺼번에 진행합니다.
https://www.acmicpc.net/problem/12986
12986번: 화려한 마을2
첫 번째 줄에 N, Q (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 수와 민호가 궁금해 하는 특정 구간의 수이다. 두 번째 줄에는 1번 집부터 N번 집까
www.acmicpc.net
이 문제와 같은 풀이입니다.
하지만 화려한 마을2 문제는 다른 조건이 있어 다른 풀이로도 풀 수 있습니다.
저는 화려한 마을3을 먼저 풀었기에 같은 풀이로 AC를 받았습니다.
|
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
95
96
97
98
99
100
101
|
#include <iostream>
#include <algorithm>
#include <cmath>
#define MAX 100001
using namespace std;
typedef struct Point {
int l, r, idx;
}Point;
Point q[MAX];
int list[MAX], ans[MAX], cnt[MAX * 2], cntCnt[MAX];
int N, 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 func() {
int l = q[1].l;
int r = q[1].r;
int ret = 0;
for (int i = l; i <= r; i++) {
int x = list[i] + 100000;
if (cnt[x]) cntCnt[cnt[x]]--;
cnt[x]++;
cntCnt[cnt[x]]++;
ret = max(ret, cnt[x]);
}
ans[q[1].idx] = ret;
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++) {
int x = list[j] + 100000;
cntCnt[cnt[x]]--;
if (!cntCnt[cnt[x]] && ret == cnt[x]) ret--;
cnt[x]--;
cntCnt[cnt[x]]++;
}
for (int j = l - 1; j >= nl; j--) {
int x = list[j] + 100000;
if (cnt[x]) cntCnt[cnt[x]]--;
cnt[x]++;
cntCnt[cnt[x]]++;
ret = max(ret, cnt[x]);
}
for (int j = r; j > nr; j--) {
int x = list[j] + 100000;
cntCnt[cnt[x]]--;
if (!cntCnt[cnt[x]] && ret == cnt[x]) ret--;
cnt[x]--;
cntCnt[cnt[x]]++;
}
for (int j = r + 1; j <= nr; j++) {
int x = list[j] + 100000;
if (cnt[x]) cntCnt[cnt[x]]--;
cnt[x]++;
cntCnt[cnt[x]]++;
ret = max(ret, cnt[x]);
}
l = nl;
r = nr;
ans[idx] = ret;
}
for (int i = 1; i <= M; i++) {
cout << ans[i] << '\n';
}
}
void input() {
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> list[i];
}
sqrtN = sqrt(N);
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 2912 백설공주와 난쟁이 (0) | 2022.09.08 |
|---|