Wonseok Shin | BOJ 13548, 수열과 쿼리 6

Solved AC Platinum 1
SAC Class 7 Essential

Contents

풀이
코드

풀이

수열과 쿼리 5 링크 와 거의 같은데, 조금 덜 자명한 문제이다.

먼저, 수열과 쿼리 5를 어떻게 푸는지 모른다면 이 글 을 권한다. Mo’s Algorithm이라는 마법의 알고리즘이 있어서, 쿼리당 $O(N)$ 이 걸리는 구간 쿼리를 오프라인에 처리함으로써 쿼리당 평균 $O(\sqrt{n})$ 비슷한 시간으로 줄여낼 수 있다. sqrt decomposition의 일종인데, 위 링크의 글이 너무 잘 쓰여 있다.

수열과 쿼리 5와는 달리, 수쿼6은 실제로 각 element가 몇개인지를 명확히 알아야 하고, 그과정에서 0인지 아닌지만 세면 되는 수쿼5와는 달리 뭔가 더 복잡한 문제가 된다.

첫번째 방법은, $x$번 나온 수가 몇 개 있는지를 세는 배열 c[x]를 정의하고, c[x] 가 nonzero인 마지막 element를 기록하는 변수를 만들어서 이를 잘 트래킹하는 것이다. 별로 어렵지는 않지만 조금 귀찮고, 이 풀이는 justicehui님의 풀이 에 잘 설명되어 있다.

두번째 방법은, 자료구조를 추가로 쓰는 것이다. 조금 느리긴 하지만, 만약 set을 쓴다고 가정하면, {i, x} 를 i가 x번 나왔다 라는 의미로 사용함으로써, $O(\log n)$ 시간에 최댓값을 찾을 수 있고, $O(\log n)$ 시간에 값을 변경할 수 있다. 다만, set을 쓰면 시간이 매우 빡빡하고 (되는지는 안 내 봤는데, 안 되지 않을까? MO의 구현체가 나보다 훨씬 빠르다면 가능할 수도 있다) 임의의 원소를 변경할 수 있는 힙을 쓰면 시간내에 구겨 들어 간다. 나는 700ms 정도 걸렸는데, $O(n \sqrt n \log n)$ 정도 복잡도는 2020년에는 $n = 1e5$면 돌아갈만 하다 :) 그러나 STL의 priority queue는 이런 연산을 지원하지 않으므로, 임의의 원소를 $O(\log n)$에 변경 가능하고 최댓값을 $O(1)$에 반환하는 heap을 직접 구현해야 한다. 어쩌다보니 같은 분이 작성하신 secmem의 이 글 에 구현된 구현체 정도면 충분하다.

코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

struct Elem
{
    int i, w;
    bool operator<(const Elem &o) const {
        return w == o.w ? i < o.i : w > o.w;
    }
};

struct PQ
{
    Elem *arr;
    int *pos;
    int sz;

    PQ(int mx) : sz(0)
    {
        arr = new Elem[mx + 1];
        pos = new int[mx + 1];
    }
    
    void push(int i, int w)
    {
        ++sz;
        arr[sz] = { i, w };
        pos[i] = sz;
        up(sz);
    }

    void change(int i, int w, bool delta = false)
    {
        int cur = pos[i];
        int k = arr[cur].w;
        int nw;
        if (delta)
            arr[cur].w += w;
        else
            arr[cur].w = w;
        nw = arr[cur].w;
        if (k > nw)
            down(cur);
        else
            up(cur);
    }

    void up(int cur)
    {
        while (cur > 1)
        {
            if (arr[cur].w <= arr[cur >> 1].w)
                break;
            swap(arr[cur], arr[cur >> 1]);
            pos[arr[cur].i] = cur;
            cur >>= 1;
        }
        pos[arr[cur].i] = cur;
    }

    void down(int cur)
    {
        while ((cur << 1) <= sz)
        {
            int mx;
            if ((cur << 1) == sz || (arr[cur << 1].w > arr[(cur << 1) + 1].w))
                mx = (cur << 1);
            else
                mx = (cur << 1) + 1;
            if (arr[cur].w >= arr[mx].w)
                break;
            swap(arr[cur], arr[mx]);
            pos[arr[cur].i] = cur;
            cur = mx;
        }
        pos[arr[cur].i] = cur;
    }

    int pop()
    {
        int ret = arr[1].i;
        arr[1] = arr[sz--];
        pos[arr[1].i] = 1;
        down(1);
        return ret;
    }

    int peek()
    {
        return arr[1].w;
    }

    void del(int i)
    {
        int cur = pos[i];
        int k = arr[cur].w;
        arr[cur] = arr[sz--];
        pos[arr[cur].i] = cur;
        if (arr[cur].w > k)
            down(cur);
        else
            up(cur);
    }
};
PQ pq(101010);
int BLK = 1;
int N, M, cur;
struct query
{
    int idx, l, r, v, ans;
    bool operator < (query &o)
    {
        if (r/BLK != o.r/BLK)
            return r / BLK < o.r/BLK;
        return l < o.l;
    }
};

struct Mo
{
    vector <int> seq;
    vector <query> Q;

    void solve()
    {
        sort(all(Q));
        int lo = 1, hi = 0;
        for (query &q : Q)
        {
            while (q.l < lo) add(--lo, q);
            while (q.r > hi) add(++hi, q);
            while (q.l > lo) sub(lo++, q);
            while (q.r < hi) sub(hi--, q);
            get_ans(q);
        }
        sort(all(Q), [](query &a, query &b) -> bool{
            return a.idx < b.idx;
        });
    }

    void add(int idx, query &q)
    {
        pq.change(seq[idx], +1, true);
    }

    void sub(int idx, query &q)
    {
        pq.change(seq[idx], -1, true);
    }

    void get_ans(query &q)
    {
        q.ans = pq.peek();
    }
};
vector <int> v;
Mo MO;
int32_t main()
{
    usecppio
    cin >> N;
    if (N <= 100) BLK = 1;
    else
        BLK = sqrt(N);
    MO.seq = vector<int>(N + 5, 0);
    for (int i = 1; i <= N; i++)
    {
        cin >> MO.seq[i];
        v.push_back(MO.seq[i]);
    }
    sort(all(v)); v.erase(unique(all(v)), v.end());
    for (int i : v)
        pq.push(i, 0);
    cin >> M;
    for (int i = 1; i <= M; i++)
    {
        int l, r; cin >> l >> r;
        MO.Q.push_back({i, l, r, 0, 0});
    }
    MO.solve();
    for (auto q : MO.Q)
        cout << q.ans << '\n';
}