[백준 2243번] [세그먼트 트리 / 이분 탐색] 사탕 상자

Approach

문제 상황을 재구성해보면 존재하는 맛 중에 경계값에 위치한 맛을 찾아주면 된다.

상황 자체는 https://viyoung.tistory.com/246 와 근본적으로 동일하다.

[백준 19646번] [세그먼트 트리] Random Generator

위 문제의 경우는, 경계값을 찾가나가되 업데이트 과정에서 해당 숫자들을 모두 지워주는 형태이다.

반면 이 문제의 경우는 -1을 업데이트 처리해주면 된다. 근본적인 문제의 접근 방법 자체는 완전히 동일하다고 볼 수 있겠다.

 

경계값을 찾아주기 위해서는 이분탐색을 진행해주면 된다. 이 과정에서 맛을 미리 좌표를 받아서 좌표 압축을 시켜서 처리하면 조금 더 효율적으로 처리할 수 있으나, 맛이 가질 수 있는 범위가 그렇게 큰 편은 아니라서 그냥 진행하였다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int seg[5000000];

void update(int node_index, int node_left, int node_right, int index, int value){
    if(index < node_left || node_right < index) return; // OUt of bound
    seg[node_index] += value;

    if(node_left == node_right) return; // Base case
    else{
        int mid = (node_left + node_right) / 2;
        update(node_index * 2, node_left, mid, index, value);
        update(node_index * 2 + 1, mid + 1, node_right, index, value);
    }
}

int query(int node_index, int node_left, int node_right, int query_right){
    int query_left = 1;
    if(node_right < query_left || query_right < node_left) return 0;
    if(query_left <= node_left && node_right <= query_right) return seg[node_index];

    int mid = (node_left + node_right) / 2;
    return query(node_index * 2, node_left, mid, query_right) +
           query(node_index * 2 + 1, mid + 1, node_right, query_right);
}

int main(void){
    fastio;
    memset(seg, 0, sizeof(seg));

    int N;
    cin >> N;

    for(int i = 0; i < N; i++){
        int t;
        cin >> t;
        // 사탕 꺼내기
        if(t == 1){
            int cmp;
            cin >> cmp;

            int start = 1;
            int end = 1000001;
            while(start < end){
                int mid = (start + end) / 2;
                if(query(1, 1, 1000000, mid) < cmp) start = mid + 1;
                else end = mid;
            }
            cout << start << "\n";
            update(1, 1, 1000000, start, -1);
        }
        else{
            int b, c;
            cin >> b >> c;
            update(1, 1, 1000000, b, c);
        }
    }
    return 0;
}