사탕상자

 

간단한 세그트리 응용 문제이다.

세그트리에는 1부터 1000000까지의 맛이 각각 몇개 들어있는지 저장하면 된다.

쿼리가 약간 다른데, 순위가 x인 사탕의 맛을 찾으려면 x가 seg[n*2]보다 크면 x에서 seg[n*2]를 빼고 seg[n*2+1]로 이동하면 되고,

작으면 seg[n*2]로 이동하면 된다.

#include<stdio.h>
int N;
long long M=1000000;
long long seg[4000004];
void update(long long n, long long s, long long e, long long ind, long long v)
{
    if(ind<s || e<ind) return;
    seg[n] += v;
    if(s!=e)
    {
        long long m = (s+e)/2;
        update(n*2,s,m,ind,v);
        update(n*2+1,m+1,e,ind,v);
    }
    return;
}
long long finds(long long n, long long s, long long e, long long v)
{
    if(s==e) return s;
    long long m = (s+e)/2;
    if(seg[n*2] < v)
    {
        return finds(n*2+1,m+1,e,v-seg[n*2]);
    }
    else
    {
        return finds(n*2,s,m,v);
    }
}
int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        int a;
        scanf("%d",&a);
        if(a==1)
        {
            long long b;
            scanf("%lld",&b);
            int x = finds(1,1,M,b);
            printf("%lld\n",x);
            update(1,1,M,x,-1);
        }
        if(a==2)
        {
            long long b,c;
            scanf("%lld %lld",&b,&c);
            update(1,1,M,b,c);
        }
    }
}

어렵지 않으니 update와 find 함수 부분만 보면 바로 이해할 수 있다.