알고리즘 공부/C++

백준 13537번 수열과 쿼리 1 C++ 세그먼트 트리, 머지 소트 트리

마달랭 2024. 8. 17. 23:53
반응형

리뷰

세그먼트 트리에 머지 소트 트리를 접목하여 범위 내 특정 값보다 큰 숫자의 개수를 출력해 주는 문제

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

 

문제 풀이

  1. n값을 입력 받고 정수형 벡터 lst에 n개의 요소를 입력 받아준다.
  2. 정수형 2차 벡터인 tree를 n * 4크기로 초기화 해준 뒤 lst를 통해 build를 진행해 준다.
  3. 이때 리프 노드는 각 lst index의 값을 갖는 길이 1짜리 정수형 벡터로 초기화 해준다.
  4. 이후 상위 노드는 merge 메서드를 사용해 각 리프 노드를 정렬된 상태로 merge하여 관리해 준다.
  5. 이후 m값을 입력 받고 m개의 쿼리를 실행해 준다. 업데이트는 없으므로 질의만 받아오게 된다.
  6. 범위와 찾을 기준이 될 값을 받아오고, query 함수에서 해당 범위를 찾았다면, 해당 노드의 전체 길이에서 val보다 큰 값을 찾은 인덱스를 빼준 값을 리턴해 주고, 이를 재귀적으로 처리해 준다.
  7. 모든 범위를 탐색 하였다면 재귀를 종료하고 해당 쿼리의 결과 값을 출력한 뒤 줄바꿈 해 준다.

 

참고 사항

각 리프 노드는 길이 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
반응형