백준 NO.13537 [수열과 쿼리 1]

Baekjoon Online Judge No.13537 [수열과 쿼리 1]

---

  문제 

13537번: 수열과 쿼리 1 (acmicpc.net)

13537번: 수열과 쿼리 1

---

  설명 

<알고리즘 분류>
 * 정렬
 * 인덱스드 트리
 * 세그먼트 트리 (Segment tree)

 

  세그먼트 트리, 인덱스드 트리를 이용하여 풀 수 있으며 이번에는 인덱스드 트리를 통해 풀어보았다. 세그먼트 트리나 인덱스드 트리에서 가장 중점은 트리의 노드를 어떻게 정의하느냐 인 것 같다.

 

  이번 문제에선 각 트리의 노드들을 단순하게 그 노드에 해당하는 수열들의 리스트를 넣어두었다. 즉, 트리의 노드들은 입력된 수열에서 영역에 맞는 하나의 부분집합을 가지고 있는 것 이다. 이 때 문제에서 요구되는 "부분수열 중에서 k보다 큰 원소의 개수" 를 파악하기 위해 트리의 초기화를 마친 후 각 노드들을 모두 오름차순으로 정렬을 하였다. 오름차순으로 정렬을 하면 결국 query 함수에서 구하고자 하는 영역 내부에 진입했을 때 upper_bound 를 통해 해당 트리의 노드에서 k 보다 큰 값의 위치를 알 수 있고, 이 위치를 그 트리의 노드 배열의 크기에서 빼 준다면 그 구간 내에서 k 보다 큰 값들의 개수를 알 수 있기 때문이다.

 

<예시>

---

  Code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> tree;
vector<int> List;
vector<int> ans;
int n, m;

int query(int curNode, int left, int right, const int tarLeft, const int tarRight, const int tar) {
	if (tarRight < left || right < tarLeft) return 0;
	if (tarLeft <= left && right <= tarRight)
		return tree[curNode].end() - upper_bound(tree[curNode].begin(), tree[curNode].end(), tar);

	int leftNode = 2 * curNode;
	int rightNode = leftNode + 1;
	int mid = (left + right) / 2;

	return (query(leftNode, left, mid, tarLeft, tarRight, tar)
		+ query(rightNode, mid + 1, right, tarLeft, tarRight, tar));
}

void update(int curNode, int left, int right, const int idx, const int val) {
	tree[curNode].push_back(val);

	if (right <= left) return;

	int mid = (left + right) / 2;
	int leftNode = 2 * curNode;
	int rightNode = leftNode + 1;

	if (idx <= mid) { // -> go left side
		update(leftNode, left, mid, idx, val);
	}
	else { // if (mid < idx) -> go right side
		update(rightNode, mid + 1, right, idx, val);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

	List.assign(n + 1, 0);
	tree.resize(4 * n);

	for (int i = 1; i <= n; i++) {
		cin >> List[i];

		update(1, 1, n, i, List[i]);
	}

	for (int i = 1; i < 4 * n; i++)
		sort(tree[i].begin(), tree[i].end());

	cin >> m;

	int s, e, tar;

	while (m--) {
		cin >> s >> e >> tar;

		ans.push_back(query(1, 1, n, s, e, tar));
	}

	for (auto e : ans) cout << e << '\n';
}