백준 13537 수열과 쿼리 1 혼내주기

 

 

 

이리저리 삽질하다가 N이 최대 100000이기 때문에 벡터로 구간 원소를 들고 있으면 되지 않을까 했는데 진짜 통과했다!
알고 보니 이런 세그트리를 머지소트 트리라고 한다.
처음에는 init 과정을 left right 순서대로 넣고 sort했는데, merge함수가 STL에 있길래 참고했다.

이번 문제는 떠올려서 풀어서 기분이 아주 좋다!@@

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

const int N = 1<<17;
vector<int> tree[N<<1];
int n, m;

void input() {
    fastio;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        int num; cin >> num;
        tree[N+i].push_back(num);
    }
    for(int i = N-1; i; --i) {
        tree[i].reserve(tree[i<<1].size() + tree[i<<1|1].size());
        auto& l = tree[i<<1];
        auto& r = tree[i<<1|1];
        merge(l.begin(), l.end(), r.begin(), r.end(), back_inserter(tree[i]));
    }
    cin >> m;
}

int query(int l, int r, int k, int i = 1, int s = 0, int e = N-1) {
    if(l > e || r < s) return 0;
    if(l <= s && e <= r) return tree[i].end() - upper_bound(tree[i].begin(), tree[i].end(), k);
    int m = (s + e) >> 1;
    return query(l, r, k, i<<1, s, m) + query(l, r, k, i<<1|1, m+1, e);
}

int main() {
    input();
    while(m--) {
        int a, b, c; cin >> a >> b >> c;
        cout << query(a-1, b-1, c) << "\n";
    }
}