백준 13537 수열과 쿼리 1 풀이

문제

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

&Title
13537번 - 수열과 쿼리 1

&Question
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 
이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.i j k: Ai, 
Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 
원소의 개수를 출력한다. 

&Input
첫째 줄에 수열의 크기 N (1 ≤ N 
≤ 100,000)이 주어진다.둘째 줄에는 A1, A2, ..., AN이 주어진다. 
(1 ≤ Ai ≤ 109)셋째 줄에는 쿼리의 개수 M 
(1 ≤ M ≤ 100,000)이 주어진다.넷째 줄부터 M개의 줄에는 
쿼리 i, j, k가 한 줄에 하나씩 주어진다. (1 
≤ i ≤ j ≤ N, 1 ≤ k 
≤ 109) 

&Output
각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다. 

&Example
-input
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2

-output
2
0
3

요약

• i - j 범위에서 k보다 큰 원소의 개수를 구하여 출력하라.

접근

• 처음으로 풀어보는 수열과 쿼리 시리즈이다. 당연히 푸는법을 몰라서 갓휘님의 풀이를 보고 풀었다.(갓휘만세!) 세그트리만 배웠다면 쉽게 이해할 수 있다.
• 일단 숫자의 범위가 1e9이기 때문에 숫자의 크기로 합트리를 만들수가 없다 ㅜㅜ
• 그렇기 때문에 다른 방법을 떠올려야 되는데 바로 mergesorttree이다..
• 세그트리를 안다면 금방 알 수 있는데, 노드가 i~j범위의 노드인 경우 i~j의 수를 다 정렬한 상태로 갖고 있는거다.
• 그럴 경우 i-j범위에서 k보다 큰 숫자의 위치만 이진탐색으로 찾는다면 그보다 큰 위치는 확정적으로 k보다 클것이다.
• 즉 범위를 나누어 k보다 큰 수를 찾는 방식이다!!
• 시간복잡도는 O(nlogn+mlog^3n)이다
• 다운탑방식인 풀이도 있지만 변태 같아서 패스~

풀이

1. 먼저 업데이트 방식을 보자 target이 start-end범위를 속하는 숫자인 경우 원소를 추가해준다.

    void update(int index, int target, int value, int start, int end) {
        if (target < start || target > end)
            return;
        tree[index].push_back(value);
        if (start != end) {
            int mid = (start + end) / 2;
            update(index * 2, target, value, start, mid);
            update(index * 2 + 1, target, value, mid + 1, end);
        }
    }
   

2. 쿼리 부분이다. tree[index].end() - upper_bound(tree[index].begin(), tree[index].end(), value); 이 부분이 머지소트트리를 이용해 k보다 큰 수를 찾는 것의 핵심이다. i-j로 범위가 좁혀지기 때문에 해당 범위들로 미리 정렬된것을 이용해 이진탐색으로 k보다 큰 수의 수를 구한다.

    int query(int index, int value, int left, int right, int start, int end) {
        if (left > end || right < start)
            return 0;
        if (left <= start && end <= right)
            return tree[index].end() - upper_bound(tree[index].begin(), tree[index].end(), value);
        else {
            int mid = (start + end) / 2;
            return query(index * 2, value, left, right, start, mid) +
                query(index * 2 + 1, value, left, right, mid + 1, end);
        }
    }
   

소스

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100001;

int n, m;
vector<int> tree[MAXN * 4];

void update(int index, int target, int value, int start, int end) {
	if (target < start || target > end)
		return;
	tree[index].push_back(value);
	if (start != end) {
		int mid = (start + end) / 2;
		update(index * 2, target, value, start, mid);
		update(index * 2 + 1, target, value, mid + 1, end);
	}
}

int query(int index, int value, int left, int right, int start, int end) {
	if (left > end || right < start)
		return 0;
	if (left <= start && end <= right)
		return tree[index].end() - upper_bound(tree[index].begin(), tree[index].end(), value);
	else {
		int mid = (start + end) / 2;
		return query(index * 2, value, left, right, start, mid) +
			query(index * 2 + 1, value, left, right, mid + 1, end);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	int val;
	for (int i = 1; i <= n; ++i) {
		cin >> val;
		update(1, i, val, 1, n);
	}
	int range = MAXN * 4;
	for (int i = 1; i < range; ++i)
		sort(tree[i].begin(), tree[i].end());
	cin >> m;
	int i, j, k;
	while (m--) {
		cin >> i >> j >> k;
		cout << query(1, k, i, j, 1, n) << '\n';
	}
	return 0;
}