백준 29447 - Выборы (C++)

문제

• 문제 링크

  
   BOJ 29447 - Выборы 
  

• 문제 요약

길이 $N$의 수열과 $Q$개의 구간 쿼리가 주어진다.
각 쿼리마다, 해당 구간에서 가장 많이 등장하는 수가 몇 번 등장했는지 출력하자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N, Q ≤ 100,000$

$1 ≤ a_i ≤ 10^9$

알고리즘 분류

• 오프라인 쿼리 (Offline Query)
• 좌표 압축 (Coordinate_Compression)
• mo's (mo's Algorithm)

풀이

BOJ 13548 - 수열과 쿼리 6 을 풀어 봤다면 이 문제역시 푼 거나 다름 없다.

단지 차이점은, $1 ≤ a_i ≤ 10^9$ 라는 것.

하지만 이 역시 $N ≤ 100,000$ 임에 따라 좌표 압축을 해주면 되기 때문에, 완전히 같은 문제가 된다.
이는 $mo's$ 로 풀 수 있는 전형적인 문제이고 앞서 언급한 문제와 동일하게 풀리기 때문에 간단히 적고 넘어 가겠다.


현재 구간 $[p, q]$ 를 보고 있을 때,

$cnt[i]$ : $i$ 가 몇 번 등장 ?

$ccnt[i]$ : $cnt[x] == i$ 가 몇 번 등장 ?

위 정보를 토대로 끝점에서 어떤 값$(val)$이 구간에 포함되려 할 때, 제거되려 할 때로 나눠 생각하자.
또, 이때 $cnt[val]$ 과 $ccnt[cnt[val]]$ 및 그 때의 답이 어떤식으로 변화하는지 정리해보는 것을 추천한다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
struct _Q
{
    int x, y, i;
    bool operator<(_Q& t)
    {
        int _x(x / 300), __x(t.x / 300);
        return _x ^ __x ? _x < __x : y < t.y;
    }
}Q[N];
int cnt[N], ccnt[N];
int V[N], ans[N];
int n, q;
 
void compression()
{
    int t[N]{}; memcpy(t, V, sizeof V);
    sort(t, t + n + 1);
 
    for (int i(1); i <= n; i++)
        V[i] = lower_bound(t, t + n + 1, V[i]) - t;
}
void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i(1); i <= n; cin >> V[i++]);
    compression();
 
    cin >> q;
    for (int i{}; i < q; i++)
    {
        auto& [x, y, _i](Q[i]);
        cin >> x >> y, _i = i;
    }
    sort(Q, Q + q);
}
void add(int& t, int val)
{
    --ccnt[cnt[val]++];
    ccnt[cnt[val]]++;
 
    if (cnt[val] > t) t = cnt[val];
}
void del(int& t, int val)
{
    if (!--ccnt[cnt[val]] && t == cnt[val])
        t--;
    ccnt[--cnt[val]]++;
}
void Query()
{
    for (int s(Q[0].x), e(s - 1), i{}, t{}; i < q; i++)
    {
        while (s > Q[i].x) add(t, V[--s]);
        while (s < Q[i].x) del(t, V[s++]);
        while (e > Q[i].y) del(t, V[e--]);
        while (e < Q[i].y) add(t, V[++e]);
        ans[Q[i].i] = t;
    }
    for (int i{}; i < q; cout << ans[i++] << '\n');
}
int main()
{
    init();
    Query();
}

comment

끝