백준 13548번: 수열과 쿼리 6

문제링크

https://www.acmicpc.net/problem/13548

13548번: 수열과 쿼리 6

풀이

• 업데이트 쿼리 없으므로 모스 알고리즘 사용
• 쿼리 시작 끝 옮기면서 원소를 추가하고 제외할 때 원소의 개수 cnt 배열과, cnt 배열의 cnt 즉 그 cnt를 가진 수의 종류의 개수를 나타내는 ccnt 배열을 관리한다.
• 추가할 때
  •  지금 가진 개수 최대값보다 추가한 원소의 개수가 더 많아지면 갱신
• 제외할 때
  1. 지금 제외하는 수가 원래 제일 많았던 수인 경우
     • 제외하기전 그 수 cnt 가 최대였고 그 수 한종류만 있었다면 (ccnt = 1) 지금 제외하는 수 cnt 따라감
     • ccnt 가 1 이상이었다면 그대로 유지
  2. 지금 제외하는 수가 제일 많은 수가 아닌 경우
     • 원래 최대 수 유지

 

코드

• 시간복잡도: $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';
    }
}