백준 13547번: 수열과 쿼리 5

문제링크

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

13547번: 수열과 쿼리 5

풀이

• 업데이트 쿼리가 없으므로 쿼리 처리 순서를 속도면에서 유리하게 바꿔서 푼다
• 원소값에 대한 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';
    }
}