반응형
리뷰
세그먼트 트리에 머지 소트 트리를 접목하여 범위 내 특정 값보다 큰 숫자의 개수를 출력해 주는 문제
https://www.acmicpc.net/problem/13537
문제 풀이
- n값을 입력 받고 정수형 벡터 lst에 n개의 요소를 입력 받아준다.
- 정수형 2차 벡터인 tree를 n * 4크기로 초기화 해준 뒤 lst를 통해 build를 진행해 준다.
- 이때 리프 노드는 각 lst index의 값을 갖는 길이 1짜리 정수형 벡터로 초기화 해준다.
- 이후 상위 노드는 merge 메서드를 사용해 각 리프 노드를 정렬된 상태로 merge하여 관리해 준다.
- 이후 m값을 입력 받고 m개의 쿼리를 실행해 준다. 업데이트는 없으므로 질의만 받아오게 된다.
- 범위와 찾을 기준이 될 값을 받아오고, query 함수에서 해당 범위를 찾았다면, 해당 노드의 전체 길이에서 val보다 큰 값을 찾은 인덱스를 빼준 값을 리턴해 주고, 이를 재귀적으로 처리해 준다.
- 모든 범위를 탐색 하였다면 재귀를 종료하고 해당 쿼리의 결과 값을 출력한 뒤 줄바꿈 해 준다.
참고 사항
각 리프 노드는 길이 1짜리 정수형 벡터이므로 이미 정렬이 된 상태이다, 상위 노드는 merge를 통해 잘 정렬되게 된다.
정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> tree;
int n, m;
void build(vector<int>& lst, int node, int start, int end) {
if (start == end) tree[node] = vector<int> (1, lst[start]);
else {
int mid = (start + end) / 2;
build(lst, node * 2, start, mid);
build(lst, node * 2 + 1, mid + 1, end);
merge(tree[node * 2].begin(), tree[node * 2].end(), tree[node * 2 + 1].begin(), tree[node * 2 + 1].end(), back_inserter(tree[node]));
}
}
int query(int node, int start, int end, int L, int R, int val) {
if (R < start || end < L) return 0;
if (L <= start && end <= R) return tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), val);
int mid = (start + end) / 2;
int left = query(node * 2, start, mid, L, R, val);
int right = query(node * 2 + 1, mid + 1, end, L, R, val);
return left + right;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
vector<int> lst(n);
tree.resize(n * 4);
for (int i = 0; i < n; i++) cin >> lst[i];
build(lst, 1, 0, n - 1);
cin >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
cout << query(1, 0, n - 1, a - 1, b - 1, c) << "\n";
}
}
728x90
반응형
'알고리즘 공부 > C++' 카테고리의 다른 글
백준 20040번 사이클 게임 C++ 유니온 파인드, 분리 집합 (0) | 2024.08.18 |
---|---|
백준 1504번 특정한 최단 경로 C++ 다익스트라, 최단 경로 (0) | 2024.08.18 |
백준 6497번 전력난 C++ MST, 최소 신장 트리 (0) | 2024.08.16 |
백준 16978번 수열과 쿼리 22 C++ 세그먼트 트리, 오프라인 쿼리 (0) | 2024.08.16 |
백준 4386번 별자리 만들기 C++ MST, 최소 신장 트리 (0) | 2024.08.15 |