BOJ 13028 - 민호의 소원 링크
(2023.07.25 기준 P2)

문제

길이가 N인 수열 A가 주어지고 구간이 주어지면 세번 이상 등장하는 수의 개수를 출력해야 하는 쿼리 Q개가 주어진다. 쿼리에 맞게 출력

알고리즘

제곱근 분할법을 이용한 mo's

풀이

수열의 값 변경이 일어나지 않는 구간 쿼리다. 그러므로 mo's를 사용하여 풀면 된다.

기본적인 틀은 BOJ 2912 - 백설공주와 난쟁이 풀이와 비슷하다.

세번 이상 등장하는 수의 종류의 개수이므로 일단 현재 범위 안에 있는 수들을 count해야 한다. 수의 범위는 최대 100,000 이라서 충분히 아무 테크닉 없이 count를 배열로 나타낼 수 있다.
세번 이상이므로 count가 3일 때마다 종류의 개수를 높히거나 낮추면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100000;

int k, ct[MAX + 1], answer[MAX];

struct Query{ // 쿼리 구조체
    int x, y, idx;

    bool operator < (const Query &that) const{
        if (this->x / k == that.x / k)
            return this->y < that.y;
        return this->x / k < that.x / k;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, Q; cin >> N >> Q;
    int A[N]; for (int i = 0; i < N; i++) cin >> A[i];

    vector<Query> queries;
    for (int i = 0, x, y; i < Q; i++){
        cin >> x >> y;
        queries.push_back({x - 1, y - 1, i});
    }

    // 제곱근 분할
    k = sqrt(N);
    sort(queries.begin(), queries.end());

    // 첫번째 쿼리의 범위부터 시작
    // 범위를 넓힐 땐 카운트가 3이 되면 등장 횟수 1 증가
    // 범위를 좁힐 땐 카운트가 3이었으면 등장 횟수 1 감소
    auto [x, y, idx] = queries[0];
    fill(ct + 1, ct + MAX + 1, 0);
    int result = 0;
    for (int i = x; i <= y; i++) if (++ct[A[i]] == 3) result++;

    answer[idx] = result;

    for (int i = 1; i < Q; i++){
        auto [X, Y, idx] = queries[i];
        while (x < X) // 왼쪽 범위 좁히기
            if (ct[A[x++]]-- == 3) result--;
        while (X < x) // 왼쪽 범위 늘리기
            if (++ct[A[--x]] == 3) result++;
        while (Y < y) // 오른쪽 범위 좁히기
            if (ct[A[y--]]-- == 3) result--;
        while (y < Y) // 오른쪽 범위 늘리기
            if (++ct[A[++y]] == 3) result++;
        answer[idx] = result;
    }

    for (int i = 0; i < Q; i++) cout << answer[i] << '\n';
}

• Python

import sys; input = sys.stdin.readline

N, Q = map(int, input().split())
A = list(map(int, input().split()))

queries = []
for i in range(Q):
    x, y = map(int, input().split())
    queries.append((x - 1, y - 1, i))

# 제곱근 분할
k = int(N ** 0.5)
queries.sort(key = lambda x: (x[0] // k, x[1]))

# 첫번째 쿼리의 범위부터 시작
# 범위를 넓힐 땐 카운트가 3이 되면 등장 횟수 1 증가
# 범위를 좁힐 땐 카운트가 3이었으면 등장 횟수 1 감소
x, y, idx = queries[0]
ct = [0] * 100001
result = 0
for i in range(x, y + 1):
    ct[A[i]] += 1
    if ct[A[i]] == 3:
        result += 1

answer = [0] * Q
answer[idx] = result

for X, Y, idx in queries[1:]:
    while x < X: # 왼쪽 범위 좁히기
        if ct[A[x]] == 3:
            result -= 1
        ct[A[x]] -= 1
        x += 1
    while X < x: # 왼쪽 범위 늘리기
        x -= 1
        ct[A[x]] += 1
        if ct[A[x]] == 3:
            result += 1
    while Y < y: # 오른쪽 범위 좁히기
        if ct[A[y]] == 3:
            result -= 1
        ct[A[y]] -= 1
        y -= 1
    while y < Y: # 오른쪽 범위 늘리기
        y += 1
        ct[A[y]] += 1
        if ct[A[y]] == 3:
            result += 1
    answer[idx] = result

print(*answer, sep = '\n')