[백준] 사탕상자(2243)

문제 링크 : [백준] 사탕상자(2243)

문제 설명

사탕 상자에 C맛 사탕을 넣고, B번째로 맛있는 사탕을 뽑는 행위를 반복합니다.

입력

N(쿼리 갯수, 1<=N<=100,000)
A_i B_i [C_i <= A_i이 2인 경우에만 입력 받음]

6
2 1 2
2 3 3
1 2
1 2
2 1 -1
1 2

출력

A_i이 1인 경우, B_i번째로 맛있는 사탕의 번호를 출력합니다.

1
3
3

카테고리

#세그먼트트리

시간 복잡도 상한

O(NlogN)까지 가능합니다.

해결 방법

1. X번째로 맛있는 사탕이라는 것은, 사탕상자에 있는 수 중, X번째로 큰 수를 출력하라는 말입니다.
2. X번째로 큰 수는 각 사탕들의 맛을 인덱스로 하는 누적합으로 쉽게 구할 수 있습니다.
3. 하지만 누적합 배열만으로는 TLE가 나옵니다.
4. 누적합은 세그먼트 트리로 쉽게 구현할 수 있습니다.
5. 세그먼트 트리에서 각 노드가 가지는 값의 의미를 잘 생각해봅니다.
6. 부분합을 위한 세그먼트 트리에서
   6-1. 왼쪽 자식 노드는 부모 노드가 커버하는 범위의 왼쪽 반 범위의 부분합을 나타냅니다.
   6-2. 오른쪽 자식 노드는 부모 노드가 커버하는 범위의 오른쪽 반 범위의 부분합을 나타냅니다.
7. 6의 성질을 이용하여, X가 왼쪽 자식의 값보다
   7-1. 작다면, 왼쪽 자식의 범위를 넘어서는 구간에서 X번째로 큰 값을 찾을 수 없으므로, 왼쪽 자식 노드의 범위 중에서 답을 찾을 수 있습니다.
   7-2. 크다면, 왼쪽 자식의 범위를 넘어서는 구간에서 X번째로 큰 값을 찾을 수 있으므로, 오른쪽 자식의 노드 범위 중에서 답을 찾을 수 있습니다.
   7-3. 7-2 경우라면, 왼쪽 노드의 범우에서 왼쪽 노드의 값만큼 X번째 수보다 작은 수가 존재하였으므로, 오른쪽 자식의 노드에서 찾을 수는 X가 아니라 "X-왼쪽 자식의 값"이 됩니다.
8. 사탕을 넣거나 빼는 방법은 일반적인 세그먼트 트리와 같습니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
using namespace std;
int n,a,b,c,d[4000004];
void u(int p,int l,int r,int x,int v){
    if(l>x||r<x)return;
    d[p]+=v;
    if(l!=r)u(p*2,l,(l+r)/2,x,v),u(p*2+1,(l+r)/2+1,r,x,v);
}
int f(int p,int l,int r,int v){
    d[p]--;
    if(l==r)return l;
    if(d[p*2]<v)return f(p*2+1,(l+r)/2+1,r,v-d[p*2]);
    else return f(p*2,l,(l+r)/2,v);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    while(n--){
        cin>>a;
        if(a&1){
            cin>>b;
            cout<<f(1,1,1000000,b)<<"\n";
        }else{
            cin>>b>>c;
            u(1,1,1000000,b,c);
        }
    }
}