[자료구조] 백준 13537번: 수열과 쿼리 1 (C++)

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

13537번: 수열과 쿼리 1

쿼리로 각 부분 수열을 구하여 k보다 큰 수의 개수를 원하기 때문에

부분 수열은 정렬되어있는 게 좋다. 그리고, 개수를 가져올 땐 정렬되어있는 것에서 이분 탐색을 하면 된다.

하지만, 부분 수열을 가져오면서 정렬을 계속하는 건 비효율적이다.

>> 머지 소트 트리를 사용한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX (100000 + 1)
#define all(v) v.begin(), v.end()
using namespace std;

vector<int> tree[MAX * 4];
vector<int> v;
int n;

// merge sort tree init function
void init(int node, int start, int end){
    if(start == end){
        tree[node].push_back(v[start]);
        return;
    }
    else{
        tree[node].resize(end - start + 1);
        int mid = (start + end) >> 1;
        init(node * 2, start, mid);
        init(node * 2 + 1, mid + 1, end);
        merge(all(tree[node * 2]), all(tree[node * 2 + 1])
        , tree[node].begin());
    }
}

int query(int node, int start, int end, int left, int right, int val){
    if(end < left || start > right) return 0;
    if(left <= start && end <= right){
        // val보다 높은 수의 개수를 물음으로 upper_bound를 사용하여
        // 해당 index를 구하여 개수를 구할 수 있음
        return tree[node].size() - (upper_bound(all(tree[node]), val) - tree[node].begin());
    }
    
    int mid = (start + end) >> 1;
    return query(node * 2, start, mid, left, right, val)
    + query(node * 2 + 1, mid + 1, end, left, right, val);
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    
    init(1, 0, n - 1);
    
    int m;
    cin >> m;
    
    vector<int> result;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        result.push_back(query(1, 0, n - 1, a - 1, b - 1, c));
    }
    
    for(int i = 0; i < result.size(); i++){
        cout << result[i] << '\n';
    }
    
    return 0;
}