[알고리즘] 백준 13544번: 수열과 쿼리 3 (C++)

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

13544번: 수열과 쿼리 3

쿼리마다 부분 배열을 정렬하여 값을 구하면

정렬 O(nlogn), 탐색 O(n), 쿼리의 수 O(m)으로

>> 시간 복잡도가 O(n^2 * logn * m)으로 시간 초과가 나게 된다.

 

그렇다고 해서 탐색을 이분 탐색으로 하기에도 이미 O(n * m)에 의해 시간 초과가 난다.

이럴 때 필요한 자료구조가 머지 소트 트리이다.

 

코드를 보면 아마 [머지 소트 트리 = 세그먼트 트리 + 머지 소트]라고 느낄 수 있다.

 

머지 소트 트리란 머지 소트 하는 과정을 각 구간 별로 노드에 담아 구간 별로 세그먼트 트리화 시킨 트리형 자료 구조다.

만들어지는 과정은 Merge Sort와 똑같이 O(NlogN)이다.

 

다만, 쿼리를 구하는 과정을 생각해보면 트리의 높이로 인한 시간 복잡도 O(logN),

탐색을 하되 이분 탐색으로 더 빠르게 하면 O(logN),

쿼리의 수 O(M)

>> O(M * (logN)^2)으로 구할 수 있다.

 

각 노드에 배열이 담기므로 트리를 2차원 배열로 선언해주어야 한다.

 

• 머지 소트 트리를 구성한 함수는 다음과 같다.

void init(int node, int start, int end){
    if(start == end) msTree[node].push_back(arr[start]);
    else{
        msTree[node].resize(end - start + 1);
        int mid = (start + end) >> 1;
        init(2 * node, start, mid);
        init(2 * node + 1, mid + 1, end);
        merge(msTree[2 * node].begin(), msTree[2 * node].end()
        ,msTree[2 * node + 1].begin(), msTree[2 * node + 1]. end()
        ,msTree[node].begin());
    }
}

분할 정복처럼 함수를 구현한다. merge() 함수를 통해 더 간편하게 구현할 수 있었다.

>> O(NlogN)

 

• 쿼리 함수

int query(int node, int start, int end, int left, int right, int val){
    if(left > end || start > right) return 0;
    
    if(left <= start && end <= right){
        return msTree[node].end() - upper_bound(msTree[node].begin()
        , msTree[node].end(), val);
    }
    
    int mid = (start + end) >> 1;
    return query(2 * node, start, mid, left, right, val)
    + query(2 * node + 1, mid + 1, end, left, right, val);
}

 

[AC 코드]

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

// n의 범위가 1~100000 >> 트리의 범위는 1~400000
// 한 노드에 배열이 들어가야 하므로 2차원 벡터로 선언
vector<int> msTree[400000 + 1];
vector<int> arr;
int n;

void init(int node, int start, int end){
    if(start == end) msTree[node].push_back(arr[start]);
    else{
        // merge 시킨 배열을 넣기위해 resize로 size 다시 할당
        msTree[node].resize(end - start + 1);
        int mid = (start + end) >> 1;
        init(2 * node, start, mid);
        init(2 * node + 1, mid + 1, end);
        // 분할 정복으로 받아낸 자식 노드(left, right) 배열을 merge
        merge(msTree[2 * node].begin(), msTree[2 * node].end()
        ,msTree[2 * node + 1].begin(), msTree[2 * node + 1]. end()
        ,msTree[node].begin());
    }
}

int query(int node, int start, int end, int left, int right, int val){
    if(left > end || start > right) return 0;
    
    if(left <= start && end <= right){
        // 더 빠르게 이분 탐색을 이용하여 탐색
        return msTree[node].end() - upper_bound(msTree[node].begin()
        , msTree[node].end(), val);
    }
    
    int mid = (start + end) >> 1;
    return query(2 * node, start, mid, left, right, val)
    + query(2 * node + 1, mid + 1, end, left, right, val);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        arr.push_back(a);
    }
    
    init(1, 0, n - 1);
    
    int last_ans = 0;
    int m;
    cin >> m;
    
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        // 쿼리에 XOR 연산
        a ^= last_ans;
        b ^= last_ans;
        c ^= last_ans;
        last_ans = query(1, 0, n - 1, a - 1, b - 1, c);
        cout << last_ans << '\n';
    }
    
    return 0;
}