[BOJ] 백준 13537번: 수열과 쿼리 1

머지 소트 트리 + 이분탐색

아래글 참고.

2020/08/17 - [알고리즘] - 머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

int n, m, k;
int arr[100001];
int mst[17][100002] = { 0, };
void make_tree(int s, int e,int depth) {
	if (s == e) {
		mst[depth][s] = arr[s];
	}
	else {
		int mid = (s + e) / 2;
		make_tree(s, mid, depth + 1);
		make_tree(mid + 1, e, depth + 1);
		int i = s, j = mid + 1;
		int idx = s;
		while (i <= mid && j <= e) {
			if (mst[depth+1][i] < mst[depth+1][j]) {
				mst[depth][idx] = mst[depth + 1][i];
				i += 1;
			}
			else {
				mst[depth][idx] = mst[depth + 1][j];
				j += 1;
			}
			idx += 1;
		}
		while (i <= mid) {
			mst[depth][idx] = mst[depth + 1][i];
			i += 1;
			idx += 1;
		}
		while (j <= e) {
			mst[depth][idx] = mst[depth + 1][j];
			j += 1;
			idx += 1;
		}
	}
}
int query(int s, int e,int depth, int num,int ds,int de) {
	if (s == ds && e == de) { // 겹침
		// 이분탐색 upper_bound
		int _s = s, _e = e;
		int mid;
		while (_s <= _e) {
			mid = (_s + _e) / 2;
			if (mst[depth][mid] > num) {
				_e = mid - 1;
			}
			else {
				_s = mid + 1;
			}
		}
		return e- _e;
	}
	int mid = (s + e) / 2;
	if (mid < ds) {
		return query(mid + 1, e, depth + 1, num, ds, de);
	}
	else if (mid >= de) {
		return query(s, mid, depth + 1, num, ds, de);
	}
	else {
		return query(s, mid, depth + 1, num, ds, mid) + query(mid + 1, e, depth + 1, num, mid + 1, de);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	make_tree(1, n,0);
	cin >> m;
	for (; m--;) {
		int s, e, c;
		cin >> s >> e >> c;			
		cout << query(1, n, 0, c, s, e) <<"\n";
	}
}