hckim

문제링크

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

풀이

• Mo's
• 각 값마다 idx 를 deque 으로 관리
• 각 값의 idx 차이 최대값 등장횟수 cnt 로 관리
• cnt를 square root decomposition 하여 탐색속도 최적화
  • bucket 먼저 찾고 그 안에서 탐색

코드

#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, K;
    cin >> N >> K;

    vector<long long> 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 a, b;
        cin >> a >> b;
        --a; --b;
        query[i] = {a, b, i};
    }

    int srqtN = sqrt(N);

    auto cmp = [&](tuple<int, int, int> p1, tuple<int, int, int> p2) {
        return get<0>(p1) / srqtN < get<0>(p2) / srqtN || (get<0>(p1) / srqtN == get<0>(p2) / srqtN && get<1>(p1) < get<1>(p2));
    };

    sort(all(query), cmp);
    
    vector<int> cnt(N, 0), bucket(N / srqtN + 1, 0);
    vector<deque<int> > pos(K + 1);
    auto include = [&](int idx) {
        int prev = -1;
        if (!pos[a[idx]].size()) pos[a[idx]].push_front(idx);
        else if (pos[a[idx]].back() < idx) prev = pos[a[idx]].back() - pos[a[idx]].front(),pos[a[idx]].push_back(idx);
        else prev = pos[a[idx]].back() - pos[a[idx]].front(), pos[a[idx]].push_front(idx);

        if (prev != -1) --cnt[prev], --bucket[prev / srqtN];
        int cur = pos[a[idx]].back() - pos[a[idx]].front();
        ++cnt[cur], ++bucket[cur / srqtN];
    };

    auto exclude = [&](int idx) {
        int prev = pos[a[idx]].back() - pos[a[idx]].front();
        --cnt[prev], --bucket[prev / srqtN];

        if (pos[a[idx]].back() == idx) pos[a[idx]].pop_back();
        else pos[a[idx]].pop_front();

        int cur = -1;
        if (pos[a[idx]].size()) cur = pos[a[idx]].back() - pos[a[idx]].front();

        if (cur != -1) ++cnt[cur], ++bucket[cur / srqtN];
    };

    auto getMax = [&]() {
        for (int i = bucket.size() - 1; i >= 0; --i) {
            if (!bucket[i]) continue;
            for (int j = (i + 1) * srqtN - 1; j >= i * srqtN; --j) {
                if (j >= cnt.size()) continue;
                if (!cnt[j]) continue;
                return j;
            }
        }
        return -1;
    };

    auto [l, r, idx] = query[0];
    for (int i = l; i <= r; ++i) {
        include(i);
    }

    vector<int> ans(M);
    for (auto [ll, rr, i]: query) {
        while (l > ll) include(--l);
        while (r < rr) include(++r);
        while (l < ll) exclude(l++);
        while (r > rr) exclude(r--);
        ans[i] = getMax();
    }
    for (auto e: ans) {
        cout << e << '\n';
    }
}

문제링크

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

풀이

• 업데이트 쿼리 없으므로 모스 알고리즘 사용
• 쿼리 시작 끝 옮기면서 원소를 추가하고 제외할 때 원소의 개수 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';
    }
}

문제링크

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

풀이

• 업데이트 쿼리가 없으므로 쿼리 처리 순서를 속도면에서 유리하게 바꿔서 푼다
• 원소값에 대한 cnt 배열 관리
  • 구간 집합에 원소가 추가되고 추가되면서 원소 cnt 가 1 이면 종류 증가
  • 구간 집합에 원소가 제거되고 제거되면서 원소 cnt 가 0 이면 종류 감소
• Mo's algorithm 으로 쿼리를 정렬하여 이전 쿼리 결과 재사용률 높임

코드

• 시간복잡도: $O((N + M)\sqrt{N}T)$
  • $T:$ 원소 추가 제거하는데 걸리는 시간 (이 문제에서는 $O(1)$)

#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> answer(M);
    vector<int> cnt(1e6 + 1, 0);
    int l = 1;
    int r = 0;
    int tmp = 0;
    for (auto [i, j, ai]: query) {
        while (i < l) tmp += ++cnt[a[--l]] == 1;
        while (i > l) tmp -= --cnt[a[l++]] == 0;
        while (j < r) tmp -= --cnt[a[r--]] == 0;
        while (j > r) tmp += ++cnt[a[++r]] == 1;
        answer[ai] = tmp;
    }

    for (auto e: answer) {
        cout << e << '\n';
    }
}