사탕상자

문제 링크

사탕상자

아이디어

• \[1 \leq \textrm{사탕의 맛} \leq 10^6\]
  • 세그먼트 트리를 구성할 수 있는 메모리 제약 조건
• 사탕의 맛 각각에 대한 버킷을 생성하고, 버킷에는 해당 버킷(즉, 사탕의 맛)에 해당하는 사탕의 개수 를 저장한다.
  • \(2\) 번 operation과 \(1\)번 operation에서 해당하는 인자를 받아서, 버킷에 저장
• 버킷의 개념을 활용하면, \(n \sim m\) 까지의 사탕의 개수를 세그먼트 트리를 활용하여 \(O(logN)\) 시간에 구할 수 있음
• \(k\) 번 째 min 값을 구하는 것은, 결국 특정 원소 보다 더 작은 \(k - 1\) 개의 원소가 존재해야하는 것을 시사한다.
  • 세그먼트 트리의 구간 정보는 해당 구간에 존재하는 사탕의 개수 를 나타낸다.
  • 루트 노드에서부터 탐색하면서, 왼쪽 구간에 존재하는 사탕의 개수가 \(k - 1\) 보다 작거나 같다면 오른쪽 구간에 \(k\) 번째 사탕이 존재한다는 뜻이다. 이 때, 왼쪽 구간에 존재하는 사탕의 개수를 절감한 개수로 오른쪽 구간에 대한 탐색을 진행해야한다.
  • 만약, 왼쪽 구간에 존재하는 사탕의 개수가 \(k\) 보다 크거나 같다면, 왼쪽 구간에 \(k\) 번째 사탕이 존재한다는 뜻이다.
• 이러한 규칙대로 진행한다면, 구간의 크기가 1인 것이 존재할텐데, 이 때가 리프노드일 때이고, \(k\) 번째 사탕의 정보가 된다.
  • 이 때, 구간 정보 \([s, s]\) 은 해당 버킷의 인덱스 그 자체를 의미하므로, 이 때 \(s\) 를 그대로 리턴한다.
  • 재귀 방식의 구현에 따라서 적절하게 처리된 다음, caller로 해당 정보가 전이된다.

소스코드

#define MAX 1000000
#include <bits/stdc++.h>
using namespace std;
namespace seg {
    int tree[4000001] = {0};

    int query(int node, int tl, int tr, const int k) {
        if (tl == tr)
            return tl;
        int tm = (tl + tr) / 2;
        if (tree[node * 2] < k) {
            return query(node * 2 + 1, tm + 1, tr, k - tree[node * 2]);
        } else {
            return query(node * 2, tl, tm, k);
        }
    }

    int mutate(int node, int tl, int tr, const int value, const int d) {
        if (value < tl || tr < value) {
            return tree[node];
        }
        if (tl == tr) {
            return tree[node] += d;
        }
        int tm = (tl + tr) / 2;
        return tree[node] = mutate(node * 2, tl, tm, value, d) + mutate(node * 2 + 1, tm + 1, tr, value, d);
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b;
        if (a == 1) {
            // extract
            int target = seg::query(1, 1, MAX, b);
            cout << target << "\n";
            seg::mutate(1, 1, MAX, target, -1);
        } else if (a == 2) {
            // mutate
            cin >> c;
            seg::mutate(1, 1, MAX, b, c);
        }
    }

    return 0;
}