BOJ 2243(사탕상자)풀이

https://www.acmicpc.net/problem/2243

2243번: 사탕상자

간단한 세그+이분 탐색 문제이다. 처음 봤을 땐 이게 어떻게 세그로 되는 건지 싶을 수 있지만

간단한 세그로 풀수 있다.

일단 1번쿼리는 나중에 생각하고 2번 쿼리부터 보자

2번 쿼리같은경우 b맛의 사탕을 c개 넣는 거니까 b, b구간에 c를 더하는 거와 같다

마이너스여도 코드에는 변화가 없으니 그냥 한 구간에 c를 더해주면 된다. 여기까진 쉬운데  1번 쿼리에서 b번째 사탕을 불러오냐가 문제가 되는데

이분 탐색에서 처음부터 mid까지 구간의 사탕 수가 b보다 같거나 크다면 무조건 왼쪽 구간에 출력할 값이 있는 것이다 그러니 right=mid를 해주면 된다.

아닐 경우 이분탐색에선 left=mid+1해 주기 때문에 똑같이 해주면 된다. 그렇게 탐색을 완료한 뒤 left를 출력하면 된다.

그리고 그게 끝이 아닌데 문제에서 보면 그 사탕을 빼주는것이니 값을 출력하고 값 위치에 -1을 더해주면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>t(4000100);
ll ln=1000000;
ll seg(ll n,ll s,ll e){
    if(s==e){return t[n]=0;}
    return t[n]=seg(n*2,s,(s+e)/2)+seg(n*2+1,(s+e)/2+1,e);
}
ll m(ll n,ll s,ll e,ll left,ll right){
    if(left>e||right<s){return 0;}
    if(left<=s&&e<=right){return t[n];}
    return m(n*2,s,(s+e)/2,left,right)+m(n*2+1,(s+e)/2+1,e,left,right);
}
ll ans(ll x){
    ll left=1;
    ll right=1000000;
    while(right-left>0){
        ll mid=(left+right)/2;
        ll s=m(1,1,ln,1,mid);
        if(s>=x)right=mid;
        else left=mid+1;
    }
    return left;
}
void h(ll n,ll s,ll e,ll i,ll f){
    if(i<s||i>e){return;}
    t[n]+=f;
    if(s!=e){h(n*2,s,(s+e)/2,i,f);h(n*2+1,(s+e)/2+1,e,i,f);}
}
int main()
{
    ll a,b,c,d,q,k,i;
    scanf("%lld",&a);
    seg(1,1,ln);
    for(i=0;i<a;i++){
        scanf("%lld %lld",&q,&c);
        if(q==1){
            ll yu=ans(c);
            printf("%lld\n",yu);
            h(1,1,ln,yu,-1);
        }else{
            scanf("%lld",&d);
            h(1,1,ln,c,d);
        }
    }
}