BOJ 2243 사탕상자

문제

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

i번째 맛의 사탕을 추가/삭제 하는 쿼리와, 상자 안에 들어있는 사탕들 중 k번째로 맛있는 사탕을 뽑는 쿼리를 처리하는 문제이다.

 

풀이

각 사탕의 맛을 인덱스로 하는 펜윅 트리로 쿼리를 처리한다.

펜윅 트리는 추가/삭제 쿼리를 $O(logN)$ 안에 할수 있다.

 

두번째 k번째 사탕을 뽑는 쿼리는 1~i까지의 사탕의 개수에 대해서 이분탐색을 해주면 된다.

사탕의 개수를 묻는 쿼리가 $O(logN)$, 이분탐색이 $O(logN)$ 이므로 2번째 쿼리를 $O(log^2N)$ 안에 처리해 줄수 있다.

시간 복잡도 : $O(Qlog^2N)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

struct BIT
{
    int n; vector<int> t;
    BIT() : n(MAXN) , t(n, 0) {}
    int sum(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=t[i]; return ret; }
    void update(int i, int dif) { for(; i<=n; i+=(i&-i)) t[i]+=dif; }
    int where(int val)
    {
        int lo=0, hi=n;
        while(lo+1<hi)
        {
            int mid=lo+hi>>1;
            if(val<=sum(mid)) hi=mid;
            else lo=mid;
        }
        return hi;
    }
};

int n;

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d", &n);
    BIT bit=BIT();

    while(n--)
    {
        int a, b, c;
        scanf("%d", &a);
        if(a==1)
        {
            scanf("%d", &b);
            printf("%d\n", bit.where(b));
            bit.update(bit.where(b), -1);
        }
        else
        {
            scanf("%d%d", &b, &c);
            bit.update(b, c);
        }
    }

    return 0;
}