https://www.acmicpc.net/problem/2243
기본문제.
<문제 설명>
사탕의 맛이 1~1e6으로 주어질 때, 최대 1e5개의 쿼리가 주어진다.
1 : k -> k번째로 맛있는 사탕의 맛 출력
2 : i d -> 맛i를 갖는 사탕의 수를 d만큼 변화
<풀이>
구간합 세그트리를 마련한다. 2번쿼리는 일반적인 세그트리 update와 같은 논리로 짜면 된다.
1번쿼리는 어떻게 짤까?
예를 들어 3번째 원소를 찾으려고 할때, 왼쪽 자식노드에 3이하가 들어있다면 왼쪽자식노드로, 3초과가 들어있다면 우측자식노드로 재귀를 진행하면 된다.
// k번째 수 찾기
int kth(int node, int st, int en, const int k) {
if (st == en) return st;
int mid = (st + en) / 2;
if (k <= seg[node * 2])
return kth(node * 2, st, mid, k);
else
return kth(node * 2 + 1, mid + 1, en, k - seg[node * 2]);
}
<전체코드>
const int SMAX = (1<<21);
int seg[SMAX];
void update(int i, int x) {
i += SMAX / 2;
seg[i] = x;
while (i > 1) {
i /= 2;
seg[i] = seg[i * 2] + seg[i * 2 + 1];
}
}
int kth(int node, int st, int en, const int k) {
if (st == en) return st;
int mid = (st + en) / 2;
if (k <= seg[node * 2])
return kth(node * 2, st, mid, k);
else
return kth(node * 2 + 1, mid + 1, en, k - seg[node * 2]);
}
int main() {
FAST;
int tt; cin >> tt;
while (tt--) {
int cmd; cin >> cmd;
if (cmd == 2) {
int box, diff; cin >> box >> diff;
update(box, seg[SMAX / 2 + box] + diff);
}
else {
int k; cin >> k;
int box = kth(1, 1, SMAX / 2 - 1, k);
cout << box << '\n';
update(box, seg[SMAX / 2 + box] - 1);
}
}
}
<생각>
1e6을 넘어서는 값에 대해선 좌표압축이 필요해 보인다
'알고리즘 > 백준 & swacademy' 카테고리의 다른 글
BOJ 14463 - 소가 길을 건너간 이유 9 (세그트리, 라인스위핑) (0) | 2020.02.29 |
---|---|
BOJ 6549 - 히스토그램에서 가장 큰 사각형 (세그트리, 분할정복, monotonic stack) (0) | 2020.02.29 |
BOJ 11982 - Angry cow (그리디, 전처리dp, 투포인터) (0) | 2020.02.27 |
BOJ 7579 - 앱 (knapsack[+]) (0) | 2020.02.25 |
BOJ 16764 - Cowpatibility (포함배제, 부분집합) (0) | 2020.02.25 |