[Algorithm] cpp 백준 13544번: 수열과 쿼리 3

[Algorithm] cpp 백준 13544번: 수열과 쿼리 3 - Merge Sort Tree

정렬된 구간 리스트를 저장한 Merge Sort Tree로 구간 [i,j]에서 k보다 큰 원소 개수를 온라인으로 계산합니다. 각 노드에서 upper_bound로 개수만 더해 O(log^2N) 질의, O(NlogN) 빌드. XOR last_ans 변형을 안전히 처리하는 구현 포인트와 엣지 케이스까지 정리합니다.

문제

링크: https://www.acmicpc.net/problem/13544
요약: 길이 \(N\)인 수열 A[1..N]이 주어질 때, 여러 쿼리마다 \([i,j]\) 구간에서 k보다 큰 원소의 개수를 출력합니다. 각 쿼리의 \(i, j, k\)는 입력의 \(a, b, c\)를 이전 정답 last_ans와 XOR하여 얻습니다(처음 last_ans = 0).
제한/스펙(요지): \(N, M \le 10^5\), 값 범위 \(\le 10^9\), 1초.

입력/출력

1
2
3
4
5
6
7
8
입력
N
A1 A2 ... AN
M
a b c  (M줄)

출력
각 쿼리마다 [i, j]에서 k보다 큰 원소의 개수를 한 줄에 하나씩 출력

접근 개요

정적 배열에 대한 순수 카운팅 질의이므로, 각 세그먼트 노드에 구간의 원소들을 “정렬된 리스트"로 저장하는 Merge Sort Tree가 적합합니다.
질의 \([i,j], k\)에서 커버되는 노드들의 리스트에 대해 upper_bound(k)로 “k보다 큰 개수"를 즉시 취합하면 됩니다.
XOR last_ans로 인해 쿼리를 재정렬할 수 없으므로, 온라인 O(log^2 N) 질의가 가능한 자료구조가 필요합니다.

flowchart TD
  A[Build: 각 노드에 정렬 리스트 저장] --> B[Query(i,j,k)]
  B --> C{세그먼트 분기}
  C -->|완전 포함| D[upper_bound로 개수 계산]
  C -->|부분 겹침| E[좌/우로 재귀 분기]
  E --> D
  D --> F[합산 결과 반환]

알고리즘 설계

빌드: 구간을 반으로 나누며 하위 노드의 정렬 리스트 두 개를 merge로 합성해 상위 노드를 구성합니다. 전체 \(O(N \log N)\).
질의: 세그먼트 트리에서 \([i,j]\)를 덮는 노드들에 대해 upper_bound(k) 위치부터 끝까지의 원소 개수를 더합니다. 노드 개수는 \(O(\log N)\), 각 노드에서 이분탐색 \(O(\log N)\) → 합계 \(O(\log^2 N)\).
정당성: 각 노드는 자신의 범위 내 값을 오름차순으로 모두 포함하며, \([i,j]\)의 분해는 서로 겹치지 않는 노드들의 합으로 표현됩니다. 따라서 노드별 “k 초과” 원소 수의 합이 정답과 일치합니다.
구현 포인트:
- 입력 배열은 1-기반으로 들고, 트리도 1-기반 인덱스로 다룹니다.
- i > j일 수 있으니 XOR 후 반드시 swap 처리.
- last_ans는 이전 쿼리의 출력으로 갱신.
- 값의 범위가 커도 정렬 리스트 기반이므로 좌표압축 불필요.

복잡도

빌드: \(O(N \log N)\)
질의: \(O(\log^2 N)\) (노드 방문 \(\log N\) × 각 노드 upper_bound \(\log N\))
공간: \(O(N \log N)\)

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct MergeSortTree {
    int n;
    vector<vector<int>> tree;

    MergeSortTree() = default;
    explicit MergeSortTree(const vector<int>& arr) { build(arr); }

    void build(const vector<int>& arr) {
        n = (int)arr.size() - 1; // arr is 1-indexed
        tree.assign(4 * n + 4, {});
        buildNode(1, 1, n, arr);
    }

    void buildNode(int node, int left, int right, const vector<int>& arr) {
        if (left == right) {
            tree[node] = { arr[left] };
            return;
        }
        int mid = (left + right) >> 1;
        buildNode(node << 1, left, mid, arr);
        buildNode(node << 1 | 1, mid + 1, right, arr);
        tree[node].resize(tree[node << 1].size() + tree[node << 1 | 1].size());
        merge(tree[node << 1].begin(), tree[node << 1].end(),
              tree[node << 1 | 1].begin(), tree[node << 1 | 1].end(),
              tree[node].begin());
    }

    // Count of elements > k in [ql, qr]
    int queryGreaterThan(int ql, int qr, int k) const {
        return queryNode(1, 1, n, ql, qr, k);
    }

    int queryNode(int node, int left, int right, int ql, int qr, int k) const {
        if (qr < left || right < ql) return 0;
        if (ql <= left && right <= qr) {
            const auto& vec = tree[node];
            auto it = upper_bound(vec.begin(), vec.end(), k);
            return (int)(vec.end() - it);
        }
        int mid = (left + right) >> 1;
        return queryNode(node << 1, left, mid, ql, qr, k)
             + queryNode(node << 1 | 1, mid + 1, right, ql, qr, k);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    MergeSortTree mst(a);

    int m;
    cin >> m;
    int last_ans = 0;

    while (m--) {
        int aa, bb, cc;
        cin >> aa >> bb >> cc;
        int i = aa ^ last_ans;
        int j = bb ^ last_ans;
        int k = cc ^ last_ans;
        if (i > j) swap(i, j);
        int ans = mst.queryGreaterThan(i, j, k);
        cout << ans << '\n';
        last_ans = ans;
    }
    return 0;
}