[C++] 평행 분할, 모스 알고리즘

평행 분할, 모스 알고리즘

평행 분할(SQRT Decomposition)은 데이터가 N개이면 √N개만큼 나눠서 관리하는 방법이다.

• 각 그룹은 대푯값을 가지고 있다. 만약 주어지는 쿼리가 구간의 덧셈이라면 그룹의 합이 대푯값이 된다.

 

평행 분할

 

모스 알고리즘은 어떤 구간 [s, e]에 속하는 원소들을 이용하여 어떤 값을 계산하는 쿼리를 처리하는 알고리즘이다.

• 업데이트가 없어 쿼리의 순서를 변경해도 무방하다. 그래서 쿼리 순서를 재배치하여 효율적으로 수행한다.
• 배열을 k(√N)개로 이루어진 그룹으로 나눠주고, 쿼리를 실행할 때 두 조건 중 하나를 만족하는 경우 먼저 처리한다.
  • [s1/k] < [s2/k]
  • [s1/k] = [s2/k] and e1 < e2

 

문제

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

13547번: 수열과 쿼리 5

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 100000;
const int MAX_VAL = 1000000;

struct QueryNode {
    int i, j, index;
    int sqrtN;

    QueryNode() : QueryNode(0, 0, -1, 0) {}
    QueryNode(int i, int j, int index, int N) : i(i), j(j), index(index) { sqrtN = sqrt(N); }

    // (s/√N, e) 순으로 오름차순 정렬
    bool operator <(const QueryNode& O)const {
        if (i / sqrtN != O.i / sqrtN)
            return (i / sqrtN < O.i / sqrtN);
        return (j < O.j);
    }
};

int N, M, A[MAX]{};
int result[MAX]{};
QueryNode Q[MAX];

int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    cin >> M;

    // 쿼리를 입력받은 후 정렬
    for (int index = 0, i, j; index < M; ++index) {
        cin >> i >> j;
        Q[index] = QueryNode(i - 1, j, index, N);
    }
    sort(Q, Q + M);

    // 첫 번째에 위치한 쿼리의 결과는 손수 구함
    int dcnt = 0, cnt[MAX_VAL + 1]{};
    int i0 = Q[0].i, j0 = Q[0].j;
    for (int i = i0; i < j0; ++i)
        if (cnt[A[i]]++ == 0)
            ++dcnt;

    result[Q[0].index] = dcnt;

    // 다음 쿼리부터 바로 이전 쿼리의 결과를 사용해 계산해 나감
    for (int i = 1; i < M; ++i) {
        while (Q[i].i < i0) if (cnt[A[--i0]]++ == 0) ++dcnt;
        while (j0 < Q[i].j) if (cnt[A[j0++]]++ == 0) ++dcnt;
        while (Q[i].i > i0) if (--cnt[A[i0++]] == 0) --dcnt;
        while (j0 > Q[i].j) if (--cnt[A[--j0]] == 0) --dcnt;
        result[Q[i].index] = dcnt;
    }

    for (int i = 0; i < M; ++i)
        cout << result[i] << "\n";
}