백준 13544 c++ "수열과 쿼리 3" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리를 이용하는 거지만

처음보는 문제 유형이다.

세그먼트 2차원 설정 즉 vector<vector<ll>> tree 방식으로 2차원 트리를 작성하는 머지소트 알고리즘을 필요로 하는 문제이다. 필자는 처음에는 이해가 안갔지만 코드를 게속 쳐보면서 이해를 시켰다.

또한 upper_bound 와 lower_bound를 언제 사용할지에 대해서도 감이 잡혔다.

좋은 문제 였다.

[코드 해설]

2. 입력 처리 (Input 함수)

Input 함수는 세그먼트 트리와 입력 데이터를 초기화합니다.

1. N 입력
   • 배열의 크기 N을 입력받습니다.
2. tree 벡터 초기화
   • 세그먼트 트리를 저장할 벡터 tree를 크기 4 * N으로 초기화합니다. 각 노드는 특정 범위를 나타내며, 이 범위에 해당하는 정렬된 값을 저장합니다.
3. arr 벡터 초기화
   • 원본 데이터를 저장할 arr 벡터의 크기를 N + 1로 설정합니다.
   • 1번부터 시작하는 인덱스를 사용하기 위해 배열 크기를 1 더 크게 설정하고, 데이터를 입력받아 저장합니다.

---

3. 세그먼트 트리 초기화 (Init_Tree 함수)

Init_Tree 함수는 세그먼트 트리를 생성하고 각 노드에 정렬된 값을 저장합니다.

1. 리프 노드 처리
   • start == end인 경우, 리프 노드에 해당하는 tree[node]에 arr[start] 값을 추가합니다.
2. 재귀 호출
   • 현재 범위를 중간 인덱스 mid를 기준으로 왼쪽 (node * 2)과 오른쪽 (node * 2 + 1) 자식 노드로 분할합니다.
   • 각 자식 노드에 대해 재귀적으로 Init_Tree를 호출합니다.
3. 병합 (Merge)
   • tree[node]를 초기화하고, 왼쪽과 오른쪽 자식 노드의 정렬된 데이터를 병합하여 저장합니다.
   • 병합된 결과는 항상 정렬된 상태로 유지됩니다.

---

4. 구간 쿼리 (Query 함수)

Query 함수는 특정 범위 [left, right] 내에서 val보다 큰 값의 개수를 반환합니다.

1. 범위 외부 처리
   • 현재 범위가 [left, right]와 겹치지 않으면 0을 반환합니다.
2. 범위 포함 처리
   • 현재 범위가 [left, right]에 완전히 포함되면, 현재 노드의 정렬된 값 중 val보다 큰 값의 개수를 계산하여 반환합니다.
     • upper_bound를 사용하여 val보다 큰 값이 처음 등장하는 위치를 찾습니다.
     • 전체 크기에서 해당 위치의 인덱스를 빼서 결과를 구합니다.
3. 재귀 호출
   • 현재 범위가 [left, right]와 부분적으로 겹치는 경우, 중간 인덱스 mid를 기준으로 왼쪽과 오른쪽 자식 노드에 대해 Query를 재귀적으로 호출합니다.
   • 두 결과를 더해 반환합니다.

---

5. 게임 진행 (Game_Start 함수)

Game_Start 함수는 사용자의 질의를 처리하고, 결과를 출력합니다.

1. 입력값 처리
   • 질의 수 M을 입력받고, 각 질의에 대해 (left, right, val)을 입력받습니다.
2. XOR 계산
   • 이전 질의 결과 last_ans를 사용하여 입력값을 XOR 연산으로 갱신합니다.
     • 이를 통해 동적 입력값을 생성하고, 연속된 질의 간 의존성을 만듭니다.
3. 구간 쿼리 호출
   • XOR 결과로 갱신된 a, b, c를 사용하여 Query를 호출합니다.
   • 결과를 last_ans에 저장하여 다음 질의에서 사용할 수 있도록 합니다.
4. 결과 출력
   • 각 질의의 결과를 출력합니다.

---

6. 메인 함수 (main)

main 함수는 프로그램의 시작점으로, 다음 작업을 수행합니다:

1. 입출력 최적화
   • ios::sync_with_stdio(false)와 cin.tie(0)를 사용하여 입출력 속도를 최적화합니다.
2. 입력 처리 및 초기화
   • Input 함수를 호출하여 데이터를 입력받습니다.
   • Init_Tree 함수로 세그먼트 트리를 초기화합니다.
3. 게임 진행
   • Game_Start 함수를 호출하여 질의를 처리하고 결과를 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

int N, M;
vector<vector<ll>> tree;
vector<ll> arr;

void Input() {
    cin >> N;
    tree.resize(N * 4);
    arr.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
}

void Init_Tree(int node, int start, int end) {
    if (start == end) {
        tree[node].push_back(arr[start]);
        return;
    }

    int mid = (start + end) / 2;
    Init_Tree(node * 2, start, mid);
    Init_Tree(node * 2 + 1, mid + 1, end);

    tree[node].resize(tree[node * 2].size() + tree[node * 2 + 1].size());
    merge(all(tree[node * 2]), all(tree[node * 2 + 1]), tree[node].begin());
}

ll Query(int node, int start, int end, int left, int right, ll val) {
    if (end < left || right < start) return 0;

    if (left <= start && end <= right) {
        return tree[node].end() - upper_bound(all(tree[node]), val);
    }

    int mid = (start + end) / 2;
    return Query(node * 2, start, mid, left, right, val) +
        Query(node * 2 + 1, mid + 1, end, left, right, val);
}

void Game_Start() {
    cin >> M;
    ll last_ans = 0;
    for (int i = 0; i < M; i++) {
        int left, right;
        ll val;
        cin >> left >> right >> val;
        ll a = (left ^ last_ans);
        ll b = (right ^ last_ans);
        ll c = val ^ last_ans;

        a = max(1LL, min(a, (ll)N));
        b = max(1LL, min(b, (ll)N));
        if (a > b) swap(a, b);

        last_ans = Query(1, 1, N, a, b, c);
        cout << last_ans << '\n';
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    Input();
    Init_Tree(1, 1, N);
    Game_Start();
}