백준 13537 - 수열과 쿼리 1

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

 

힌트 1

수열의 원소를 바꾸는 연산은 없다.

힌트 2

수열의 갱신이 없는 상태에서 특정 구간의 원소 index를 빠르게 찾기 위해 Merge Sort Tree를 이용할 수 있다.

---

풀이

수열이 주어지고 특정 구간에서 k보다 큰 원소를 찾는 연산을 최대 10만 번 수행한다.

 

따라서 해당 연산을 빠르게 수행할 필요가 있고, Merge Sort Tree가 이를 가능케 한다.

 

머지 소트 트리를 구현해서 k보다 큰 원소가 나타나는 index를 upper bound로 찾으면 특정 구간에서 k 이하 원소의 개수를 확보할 수 있다.

 

우리는 k보다 큰 원소의 갯수를 알고 싶으므로 (구간의 길이 - 머지 소트 트리의 질의로 찾은 k 이하 원소의 개수)를 출력하면 AC를 받을 수 있다.

 

시간 복잡도: $O(N\log^{2}N)$

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int n;
int ar[100001];
vector<int> tree[400001];

inline int mid(int s, int e) { return s + (e - s) / 2; }

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

    int m = mid(start, end);
    init(node * 2, start, m);
    init(node * 2 + 1, m + 1, end);

    vector<int> &l = tree[node * 2];
    vector<int> &r = tree[node * 2 + 1];
    tree[node].resize(l.size() + r.size());
    merge(l.begin(), l.end(), r.begin(), r.end(), tree[node].begin());
}

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

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

    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> ar[i];
    init(1, 1, n);
    int q;
    cin >> q;
    while (q--)
    {
        int a, b, c;
        cin >> a >> b >> c;

        cout << (b - a + 1) - query(1, 1, n, a, b, c) << '\n';
    }
}