코드 복사/붙여넣기 하는 당신이 아름답습니다.

7469 : K번째 숫자

풀이

구간합 트리를 쫌 변형해보자.

구간합 트리는 [lft, rgt] 구간에 있는 원소들의 합을 관리한다.

여기서! 원소들의 합원소들로 바꿔서 관리해주자!

노드를 int: 구간합이 아니라 vector: 구간의 원소들로 관리하는 거다.

구간을 실체화 시켰다고 하면 될라나?

노드가 2*n개이므로 메모리는 O(n log n)으로 충분하다!

이제 각각의 벡터에는 [lft, rgt] 구간의 원소들이 들어있게 되었고,

이제 각각의 벡터를 정렬해주자.

그리고 쿼리가 들어오면, [s, e] 구간에서 x번째 수가 무엇인지 찾아낼 것이다.

그 수를 이분탐색으로 찾아줄 건데 이건 코드를 보는 편이 더 이해하기 쉬울 것 같다.

구간합 쿼리에서 (구간합 + 구간합) 해주던 걸 (upperbound + upperbound)로 바꿔주자!

끝!

코드

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

const int n_ = 140000;

int n, q;
int arr[n_];
vector<int> tree[n_ * 2 + 2];

void upd(int now, int idx, int lft, int rgt, int x) {
	if (idx < lft || rgt < idx) return;
	tree[now].push_back(x);
	if (lft != rgt) {
		upd(now * 2, idx, lft, (lft + rgt) / 2, x);
		upd(now * 2 + 1, idx, (lft + rgt) / 2 + 1, rgt, x);
	}
}

int qry(int now, int bgn, int end, int lft, int rgt, int x) {
	if (rgt < bgn || end < lft) return 0;
	if (bgn <= lft && rgt <= end) return upper_bound(tree[now].begin(), tree[now].end(), x) - tree[now].begin();
	return qry(now * 2, bgn, end, lft, (lft + rgt) / 2, x) + qry(now * 2 + 1, bgn, end, (lft + rgt) / 2 + 1, rgt, x); // baekjoon님 이 코드를 BOJ에서 보고 계신다면 저를 BOJ에서 밴 해 주십시오
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        upd(1, i, 1, n, arr[i]);
    }

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

    while (q--) {
        int s, e, x;
        scanf("%d %d %d", &s, &e, &x);
        int l = -1e9, r = 1e9;
        while (l <= r) {
            int m = (l+r)/2;
            if (qry(1, s, e, 1, n, m) < x) l = m + 1;
            else r = m - 1;
        }
        printf("%d\n", l);
    }

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-08-27 20:24

Read more posts by this author