문제링크
https://www.acmicpc.net/problem/13548
13548번: 수열과 쿼리 6
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다.
www.acmicpc.net
풀이
- 업데이트 쿼리 없으므로 모스 알고리즘 사용
- 쿼리 시작 끝 옮기면서 원소를 추가하고 제외할 때 원소의 개수 cnt 배열과, cnt 배열의 cnt 즉 그 cnt를 가진 수의 종류의 개수를 나타내는 ccnt 배열을 관리한다.
- 추가할 때
- 지금 가진 개수 최대값보다 추가한 원소의 개수가 더 많아지면 갱신
- 제외할 때
- 지금 제외하는 수가 원래 제일 많았던 수인 경우
- 제외하기전 그 수 cnt 가 최대였고 그 수 한종류만 있었다면 (ccnt = 1) 지금 제외하는 수 cnt 따라감
- ccnt 가 1 이상이었다면 그대로 유지
- 지금 제외하는 수가 제일 많은 수가 아닌 경우
- 원래 최대 수 유지
- 지금 제외하는 수가 원래 제일 많았던 수인 경우
코드
- 시간복잡도: $O(MlogM + (N + M)\sqrt N)$
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vector<int> a(N);
for (auto& e: a) {
cin >> e;
}
int M;
cin >> M;
vector<tuple<int, int, int> > query(M);
for (int i = 0; i < M; ++i) {
int l, r;
cin >> l >> r;
query[i] = {l - 1, r - 1, i};
}
int sqrtN = sqrt(N);
auto cmp = [&](tuple<int, int, int>& t1, tuple<int, int, int>& t2) {
return get<0>(t1) / sqrtN < get<0>(t2) / sqrtN || (get<0>(t1) / sqrtN == get<0>(t2) / sqrtN && get<1>(t1) < get<1>(t2));
};
sort(all(query), cmp);
vector<int> cnt(1e5 + 1, 0);
vector<int> ccnt(N + 1, 0);
int l = 1;
int r = 0;
int maxCnt = 0;
auto include = [&](int num) {
--ccnt[cnt[num]];
++cnt[num];
++ccnt[cnt[num]];
maxCnt = max(maxCnt, cnt[num]);
};
auto exclude = [&](int num) {
--ccnt[cnt[num]];
--cnt[num];
++ccnt[cnt[num]];
if (!ccnt[maxCnt]) {
maxCnt = cnt[num];
}
};
vector<int> answer(M);
for (auto& [i, j, ai]: query) {
while (i < l) include(a[--l]);
while (i > l) exclude(a[l++]);
while (j < r) exclude(a[r--]);
while (j > r) include(a[++r]);
answer[ai] = maxCnt;
}
for (auto& e: answer) {
cout << e << '\n';
}
}728x90
'PS > BOJ' 카테고리의 다른 글
| 백준 4008번: 특공대 (0) | 2022.03.06 |
|---|---|
| 백준 16978번: 수열과 쿼리 22 (0) | 2022.03.02 |
| 백준 1420번: 학교 가지마! (0) | 2022.02.26 |
| 백준 10254번: 고속도로 (0) | 2022.02.26 |
| 백준 13547번: 수열과 쿼리 5 (0) | 2022.02.25 |