boj 13537 수열과 쿼리 1

www.acmicpc.net/problem/13537

13537번: 수열과 쿼리 1

i j k -> 배열의 i ~ j 번째 중에서 k보다 큰 수의 갯수를 출력하는 문제입니다.

저는 N개의 배열을 세그먼트트리에 저장해주고 각 구간에 포함되는 인덱스의 수를 벡터에 넣었습니다.

그리고 트리의 모든 범위를 한번씩 정렬해줍니다. (k보다 큰 수의 갯수를 찾기 위함입니다)

 

i j k 입력이 들어오면 query함수에서 찾아줍니다.

현재 들어와있는 구간[s, e]이 찾는 구간[l, r] 밖에 있으면 0을 리턴시켜주고,

완전히 포함되어있으면 tree[node]의 end - upper_bound를 리턴시켜줍니다.

 

end는 마지막원소 +1의 위치를 반환해주고,

upper_bound는 k 값을 초과하는 첫번째 숫자의 위치를 반환해줍니다.

따라서 k보다 큰 원소의 갯수를 구하려면 end - upper_bound를 해주시면 됩니다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> tree[400004];
int N, M;
 
void update(int node, int s, int e, int idx, int diff) {
    if (s > idx || e < idx) return;
    tree[node].push_back(diff);
    if (s == e) return;
 
    int m = (s + e) / 2;
    update(node * 2, s, m, idx, diff);
    update(node * 2 + 1, m + 1, e, idx, diff);
}
 
int query(int node, int s, int e, int l, int r, int x) {
    if (s > r || e < l) return 0;
    if (l <= s && e <= r) return tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), x);
 
    int m = (s + e) / 2;
    return query(node * 2, s, m, l, r, x) + query(node * 2 + 1, m + 1, e, l, r, x);
}
 
void func() {
    int i, j, k;
    cin >> M;
    while (M--) {
        cin >> i >> j >> k;
        cout << query(1, 1, N, i, j, k) << '\n';
    }
}
 
void input() {
    int x;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> x;
        update(1, 1, N, i, x);
    }
 
    for (int i = 1; i <= N * 4; i++) sort(tree[i].begin(), tree[i].end());
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}