풀이
구간합 트리를 쫌 변형해보자.
구간합 트리는 [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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이