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

2243번: 사탕상자

세그먼트 트리

---

이 문제는 array값이 주어지지 않는다.

 

그럼 트리를 어떻게 만드는가?

사탕의 맛이 1부터 1,000,000 까지의 정수로 표현된다고 한다.

그래서 사탕의 맛을 트리의 인덱스(구간)로 설정하면 되고 사탕의 맛의 개수를 트리의 값으로 설정하면 풀 수 있다.

 

 

[백준 1321] 군인 C++

 

트리 모델링을 했다면 위 문제와 비슷하게 풀면 된다.

 

사탕을 입력할 때는 입력받은 사탕의 맛(트리의 구간(인덱스))이 존재하는 구간에 입력하는 개수만큼 재귀적으로 더해준다.

사탕을 꺼낼 때는 자식 노드의 값(구간의 사탕의 개수)을 통해 재귀 탐색할 위치를 정해준다.

찾고자 하는 사탕의 순위가 왼쪽 트리의 값(1순위부터 저장됨) 이하라면 왼쪽으로 탐색해야한다.

아니라면 오른쪽 트리를 탐색해 나간다.

 

찾고자 하는 순위에 도달하면 (양쪽 인덱스가 동일해지면) 현재 맛의 번호(인덱스)를 출력하고 재귀적으로 되돌아가며 지나온 노드의 값을 1씩 빼주면 된다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
#define MAX 1000001
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N;
int tree[MAX * 4];
 
int make_tree(int startidx, int endidx, int node){
    if(startidx == endidx) return tree[node] = 0;
    int mid = (startidx + endidx) / 2;
    return tree[node] = make_tree(startidx, mid, node*2) + make_tree(mid+1, endidx, node*2+1);
}
 
// A : 2 -> 사탕 넣는 경우
void update(int startidx, int endidx, int node, int flavornum, int up){
    if(flavornum < startidx || flavornum > endidx) return;
    tree[node] += up;
    if(startidx == endidx) return;
    int mid = (startidx + endidx) / 2;
    update(startidx, mid, node*2, flavornum, up);
    update(mid+1, endidx, node*2+1, flavornum, up);
}
 
// A : 1 -> targetnum 순위의 사탕 꺼냄
void getQuery(int startidx, int endidx, int node, int targetnum){
    if(startidx == endidx){
        cout << startidx << "\n";
        tree[node]--;
        return;
    }
    int leftnum = tree[node*2];
    int mid = (startidx + endidx) / 2;
    
    if(targetnum <= leftnum) getQuery(startidx, mid, node*2, targetnum);
    else getQuery(mid+1, endidx, node*2+1, targetnum - leftnum);
    
    tree[node]--;
}
 
void solve(){
    cin >> N;
    int A, B, C;
    for(int i = 0; i < N; i++){
        cin >> A;
        if(A == 1){
            cin >> B;
            getQuery(1, MAX, 1, B);
        }
        else{
            cin >> B >> C;
            update(1, MAX, 1, B, C);
        }
    }
}
 
int main(){
    fastio
    solve();
    
    return 0;
}