BOJ 2243 - 사탕상자

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

문제 소개

두가지 행동을 하는 문제이다.

1. x 맛의 사탕의 갯수를 k개 변화시킨다. 
2. k번째로 맛있는 사탕의 맛 수치를 출력한다. (1이 가장 맛있고 1000000이 최악)

문제 풀이

1번 쿼리는 굉장히 자주 나오는 쿼리이고 하나도 까다롭지 않게 작용한다. 중요한 것은 2번쿼리로 그니까 1부터 순서대로 늘어놓았을 때 k번째 숫자를 구하고 싶은 것이다. 

구간 합 구하기의 가장 간단한 세그를 생각해보면 우리가 얻은 수 있는 값은 구간 의 합이다. 이 문제는 세그에는 추가적인 옵션을 가하지 않고, 이 값을 이용하여 문제를 해결할 수 있다.

이분 탐색이다. 1~i 구간의 합을 구할 수 있다. 그 값이 k이하인지 초과인지에 따라서 k번째 숫자가 i이하인지 초과인지 구할 수 있다. 따라서 lgM (M은 맛 수치의 범위)번의 질문을 통해서 k번째 숫자를 구할 수 있고, 한번의 질문에 답을 하는데 걸리는 시간 복잡도는 $O(lgM)$이므로 총 시간 복잡도 $O(Mlg^2M)$의 시간복잡도에 전체 문제를 해결할 수 있다. 세그에 이분탐색을 하는 테크닉은 각각의 테크닉이 활용도가 높아 전체 활용도도 굉장히 높다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll tree[4040404];
 
void upt(ll idx,ll val,ll s,ll e,ll nod){
    if(idx<s||idx>e) return ;
    tree[nod]+=val;
    if(s==e) return;
    upt(idx,val,s,(s+e)/2,nod*2);
    upt(idx,val,(s+e)/2+1,e,nod*2+1);
}
 
ll val(ll l,ll r,ll s,ll e,ll nod){
    if(r<s||e<l) return 0;
    if(l<=s&&e<=r) return tree[nod];
    return val(l,r,s,(s+e)/2,nod*2)+val(l,r,(s+e)/2+1,e,nod*2+1);
}
 
ll sol(ll ans){
    ll lo=0,hi=1000001;
    while(lo<hi){
        ll mid=(lo+hi)/2;
        if(val(1,mid,1,1000000,1)<ans) lo=mid+1;
        else hi=mid;
        //printf("%lld %lld %lld %lld\n",lo,mid,hi,ans);
    }
    return lo;
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld",&n);
    while(n--){
        ll a,b,c;
        scanf("%lld",&a);
        if(a==1){
            scanf("%lld",&b);
            ll ans=sol(b);
            printf("%lld\n",ans);
            upt(ans,-1,1,1000000,1);
        }
        else{
            scanf("%lld %lld",&b,&c);
            upt(b,c,1,1000000,1);
        }
    }
}