c++ 13537번 수열과 쿼리 1 (백준)

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

using namespace std;

int arr[100001]; //입력을 받을 배열
vector<int> tree[400001]; //노드를 벡터로 구성

void update(int s, int e, int node, int index, int val) { //머지 소트 트리 수정
	if(s > index || e < index) return;
	tree[node].push_back(val); //요소를 노드에 추가합니다.
	if(s == e) return;
	int m = (s+e)/2;
	update(s, m, node*2, index, val);
	update(m+1, e, node*2+1, index, val);
}

int find(int s, int e, int node, int l, int r, int key) { //머지 소트 트리 찾기
	if(s > r || e < l) return 0;
	if(l <= s && e <= r) {
    	//upper_bound (노드에서 key값과 이하인 요소들의 개수를 구합니다)
        //초과가 없다면 tree[node].size(), 모든 요소가 key보다 크다면 0 입니다.
		int left = 0;
		int right = tree[node].size();
		int mid;
		while(left < right) {
			mid = (left+right)/2; 
			if(tree[node][mid] <= key) left = mid+1;
			else right = mid;
		}
		return tree[node].size() - right; //(전체 요소 개수 - key값보다 이하인 요소들의 개수  = key값보다 초과인 요소들의 개수
	}
	int m = (s+e)/2;
	return find(s, m, node*2, l, r, key) + find(m+1, e, node*2+1, l, r, key);
}

int main(void) {
	int n, m;
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		scanf("%d", &arr[i]); //요소를 입력받고
		update(1, n, 1, i, arr[i]); //머지 소트 트리를 수정합니다.
	}
	
	for(int i=1; i<=400000; i++) { //모든 노드들을 오름차순 정렬합니다.
		sort(tree[i].begin(), tree[i].end());
	}
	
	scanf("%d", &m); //테스트케이스
	while(m--) { 
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c); //입력받기
		printf("%d\n", find(1, n, 1, a, b, c)); //a~b에서 c값을 초과하는 것의 개수들을 출력
	}
}

 

풀이 : merge sort tree

 

0. 입력을 받을 배열, 트리들의 노드를 구성할 벡터들을 준비하고, merge sort tree에 대한 함수들을 준비합니다.

1. 요소들을 입력 받으면서 merge sort tree을 수정합니다.

2. 모든 merge sort tree들의 노드들을 오름차순으로 정렬합니다. (algorithm의 sort() 함수를 사용합니다)

3. 쿼리를 실행합니다.

4. find에서는 upper_bound을 이용하여 벡터에서 key보다 큰 값이 몇개인지를 구한 다음 리턴하는 방식을 사용합니다.

4.1 upper_bound는 원래 key값보다 더 큰 값중 가장 앞에있는 index을 찾습니다.

      이 index는 key값보다 이하인 요소들의 개수로도 볼 수 있습니다.

      이 값을 노드의 요소의 개수에 빼면 key값 초과인 요소들의 개수를 구할 수 있습니다.

 

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

13537번: 수열과 쿼리 1