[백준 2243] 사탕상자 (C++)

문제 링크: www.acmicpc.net/problem/2243

2243번: 사탕상자

1. 주의할 점

- 세그먼트 트리에 대해 알고 있어야 한다

- 우선순위가 높은 사탕을 뽑을 방법은?

 

2. 구현

- Tree[]를 이용하여 세그먼트 트리를 구성한다. 이때, Tree의 크기는 사탕의 우선순위가 1~1000000이므로 N=1000000일때 완전이진트리의 높이를 구하고, 비트연산으로 배열의 메모리를 동적으로 할당한다

- Update() 함수를 통해 idx가 포함된 경우, Tree[]를 갱신한다

- findIdx() 함수를 통해 부분합을 이용하여 val의 우선순위에 해당하는 사탕 값을 반환한다

 

#define MAX 1000000
#include <iostream>
#include <cmath>
long long *tree;
using namespace std;

int findIdx(int node, int left, int right, int val){
    if(left==right){
        cout<<left<<'\n';
        return left;
    }
    int mid = left + (right-left)/2;
    if(tree[node*2]<val)
        return findIdx(2*node+1,mid+1,right,val-tree[node*2]);
    else 
        return findIdx(2*node,left,mid,val);
}

void update(int node, int start, int end, int idx, long long diff){
    if(start > idx || end < idx) return;
    tree[node]+=diff;
    if(start==end) return;
    int mid = start+(end-start)/2;
    update(2*node,start,mid,idx,diff);
    update(2*node+1,mid+1,end,idx,diff);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    long long query,a,b,c,height;
    height = ceil(log2(MAX));
    tree = new long long[1<<(height+1)];
    cin >> query;
    for(int i=0;i<query;i++){
        cin>>a>>b;
        if(a==1){
            int idx = findIdx(1,1,MAX,b);
            update(1,1,MAX,idx,-1);
        }
        else{
            cin>>c;
            update(1,1,MAX,b,c);
        }
    }
    return 0;
}