boj, 백준) 13537. 수열과 쿼리1 (C++)

1. 문제 링크

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

13537번: 수열과 쿼리 1

 

2. 문제 개요

길이가 N인 수열 A1, A2,..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오

i j k : Ai , Ai+1,..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.

 

 

3. 문제 풀이

시간복잡도를 분석해보자 그냥 단순하게 매 번 탐색을 한다고 가정하면,

구간 최대O(N), 횟수 O(M)이므로 시간 복잡도는 O(NM)이고 10^10으로 시간 초과가 될 것이다. 

그러면, 쿼리를 log n의 시간대로 줄여볼 수는 없을까?

 

세그먼트의 트리로 전처리를 할 것이다. 이 경우 각 노드는 어떤 정보를 가지고 있어야 할까.

흔히 가장 기본적으로 알려진 부분합 구하는 세그먼트 트리를 생각해보자.

 

세그먼트 트리를 초기화할때, 각 노드까지 접근하는 시간 logn 각 노드마다 초기화 및 값을 return 하면서 root까지 다시 올라오기 때문에 n개, 즉 가장 노멀한 경우 초기화하는데 걸리는 시간은 O(nlogn)이다.

 

이번 문제에서는 Merge sort처럼 각 부분을 정렬하면서 올라올 것이다. 그러면 세그먼트 트리를 초기화하는데 드는 시간 복잡도는, 각 원소에 접근 log n, 정렬하면서 올라오지만 Merge sort의 특성상 값을 단순히 복사하면서 올라오는 것이기 때문에 n번, 따라서 이 경우도 O(nlogn)이 될 것이다.

 

문제의 예인

5

5 1 2 3 4로 만든다고 가정하면

 

그림판이라...ㅠ

과 같은 형태가 될 것이다.

 

 

자 이렇게 만들어 두었고, 어떻게 쿼리를 받을 것인가에 대해 생각해보자.

M개의 쿼리에 대해서 1개의 쿼리가 O(logn)의 시간에 끝나야 제 한 시간 내에 처리할 수 있다.

따라서 각 부분 범위에 대해 특정 값 x보다 큰 개수를 셀 때 이분 탐색을 통해서 세어야 한다.

 

각 노드들은 정렬된 채 저장되기 때문에 이분 탐색 적용이 가능하다.

upperbound는 어떤 범위에서, 특정값 x보다 큰 가장 작은 정수의 iterator를 반환하기 때문에 node.end() - iter를 해주면 특정 값 x보다 큰 원소의 개수를 구할 수 있다.

이렇게 되면 logn만큼 탐색하고, log n의 시간 복잡도로 탐색을 하기 때문에 제한시간 내에 수행할 수 있다.

 

 

 

4. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int n, m;
vector<int> arr;

class Segment_tree {
	public:
		Segment_tree() {}
		Segment_tree(int tree_size) { tree.resize(tree_size); }

		vector<int> init_tree(int cur, int start, int end, int left, int right)
		{
			if (start == end) {
				tree[cur].push_back(arr[start]);
				return tree[cur];
			}
			
			int mid = (start + end) / 2;

			tree[cur] = init_tree(cur * 2, start, mid, left, right);
			vector<int> append = init_tree(cur * 2 + 1, mid + 1, end, left, right);

			tree[cur].insert(tree[cur].end(), append.begin(), append.end());
			sort(tree[cur].begin(), tree[cur].end());

			return tree[cur];
		}

		int find_tree(int cur, int start, int end, int left, int right, int val)
		{
			if (end < left || right < start)
				return 0;

			if (left <= start && end <= right) {
				int temp = tree[cur].end() - upper_bound(tree[cur].begin(), tree[cur].end(), val);
				return tree[cur].end() - upper_bound(tree[cur].begin(), tree[cur].end(), val);
			}

			int mid = (start + end) / 2;

			return find_tree(cur * 2, start, mid, left, right, val) + find_tree(cur * 2 + 1, mid + 1, end, left, right, val);

		}
		vector<vector<int>> tree;
};

int main()
{
	scanf("%d", &n);
	arr.resize(n);
	
	for (int i = 0; i < n; ++i)
		scanf("%d", &arr[i]);

	int h = (int)ceil(log2(n));
	int tree_size = 1 << (h + 1);	//1~2^h+1 -1 = 2^(h+1) -1개

	Segment_tree sgt(tree_size);
	sgt.init_tree(1, 0, n - 1, 0, n - 1);

	scanf("%d", &m);
	for (int i = 0; i < m; ++i) {
		int left, right, val;
		scanf("%d %d %d", &left, &right, &val);
		printf("%d\n", sgt.find_tree(1, 0, n - 1, left-1, right-1, val));	//내 arr은 0부터 시작하므로..
	}


	return 0;
}

 

5. 결과