BOJ : 13537 수열과 쿼리 1

---

[BOJ 13537(P4)리뷰]

유명한 수열과 쿼리 1번문제다. 세그먼트 트리 + 이분탐색을 이용하여 문제를 해결할 수 있다.

세그먼트 트리를 구성할때 각 부모노드들은 자식의 값들을 정렬된 상태로 갖는 형태여서 머지소트 트리 라고도 불리는 것 같다. 이렇게 트리를 구성함으로 우리는 각 구간별 정렬된 값들을 가질 수 있다.

쿼리가 들어오면 구간을 확인한 후에 K보다 큰 값들의 개수를 출력하면 된다. 정렬된 상태이기 때문에 upper_bound를 통해 쉽게 구할 수 있다.

1. 구간에 맞지 않는 경우
2. 구간에 걸친 경우
3. 구간에 완전히 속하는 경우

위 세가지의 경우로 처리하여 반환되는 값들의 합을 출력하면 정답처리를 받을 수 있다.

/*
	21.01.25
	BOJ : 13537 수열과 쿼리 1  (https://www.acmicpc.net/problem/13537)
	세그먼트 트리
*/
#include <bits/stdc++.h>
using namespace std;

vector <int> tree[300000];
int n,m;
int s;

void init(int node, int index, int val, int left, int right) {
	if (index >= left && index <= right) {
		tree[node].push_back(val);

		if (left != right) {
			int mid = (left + right) / 2;
			init(node * 2, index, val, left, mid);
			init(node * 2 + 1, index, val, mid + 1, right);
		}
	}
}

int query(int node, int left, int right, int qleft, int qright, int val) {
	if (qleft > right || left > qright) return 0;
	else if (left >= qleft && right <= qright) { //완전 포함
		int cnt = tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), val);
		return cnt;
	}
	else {
		int mid = (left + right) / 2;
		int cnt = query(node * 2, left, mid, qleft, qright, val) + query(node * 2 + 1, mid + 1, right, qleft, qright, val);
		return cnt;
	}

}

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

	cin >> n;
	s = ceil(log2(n));
	s = (1 << s);

	for (int i = 1; i <= s; i++) {
		if (i <= n) {
			int val;
			cin >> val;
			init(1, i, val, 1, s);
		}
		else {
			init(1, i, INT_MAX, 1, s);
		}
	}

	for (int i = 1; i < 2 * s; i++) {
		sort(tree[i].begin(), tree[i].end());
	}

	cin >> m;

	while (m--) {
		int l, r, v;
		cin >> l >> r >> v;

		cout << query(1, 1, s, l, r, v) <<'\n';
	}


	return 0;
}