BOJ)13548 수열과 쿼리 6

문제: icpc.me/13548

길이가 N인 수열이 주어질 때 구간 i j 사이에 가장 많이 등장한 수가 몇번 등장했는지 출력하는 문제이다.

이 문제를 온라인으로 수행하려고하면 굉장히 힘들어 보인다. 하지만 업데이트가 이루어지지 않기 때문에 오프라인 쿼리 문제로 변형시켜서 풀어볼 수 있다.

따라서 이 문제를 mo's algorithm을 이용하여 풀건데 가장 많이 등장하는 수를 결정해야 하기 때문에 현재까지 가장 많이 등장하는 수를 계속 가지고 있어야하고

각각의 수가 몇번 등장하였나 배열을 a, i번 등장한 수가 몇개 있나 배열을 b에 각각 저장해두면 

현재 쿼리의 답이 x면 만약 add로 인하여 추가 된 b가 x보다 크다면 x를 증가시켜주고 

erase로 인하여 x만큼 등장한 수가 없어진다면 x를 감소시켜주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, sz, a[100010], ans[100010], curr, cnt[100010], b[100010];
struct qry {
    int lo, hi, idx;
    qry(int lo, int hi, int idx) :lo(lo), hi(hi), idx(idx) {};
    qry() {}
    bool operator<(const qry& x) {
        int lidx = hi / sz;
        int ridx = x.hi / sz;
        return lidx == ridx ? lo < x.lo : lidx < ridx;
    }
}q[100010];
void add(int num) {
    if (cnt[num])
        b[cnt[num]]--;
    cnt[num]++;
    b[cnt[num]]++;
    curr = max(curr, cnt[num]);
}
void erase(int num) {
    b[cnt[num]]--;
    if (cnt[num] == curr&&!b[cnt[num]])
        curr--;
    cnt[num]--;
    b[cnt[num]]++;
}
int main() {
    scanf("%d", &n);
    sz = sqrt(n);
    for (int i = 0; i < n; i++)scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        q[i] = qry(x - 1, y - 1, i);
    }
    sort(q, q + m);
    int lo = 0, hi = 0;
    add(a[0]);
    for (int i = 0; i < m; i++) {
        auto &next = q[i];
        int nlo = next.lo, nhi = next.hi;
        for (int i = lo; i < nlo; i++)
            erase(a[i]);
        for (int i = lo - 1; i >= nlo; i--)
            add(a[i]);
        for (int i = hi + 1; i <= nhi; i++)
            add(a[i]);
        for (int i = hi; i > nhi; i--)
            erase(a[i]);
        lo = nlo;
        hi = nhi;
        ans[next.idx] = curr;
    }
    for (int i = 0; i < m; i++)
        printf("%d\n", ans[i]);
    return 0;
}