퀘스트 중인 모험가 - 15816

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, M;
int aidx;
int arr[2000001];
queue<int> first;
queue<pair<int, pair<int, int>>> q;
 
struct FenwickTree
{
    vector<int> tree;
 
    FenwickTree(int n) : tree(n, 0) {}
 
    int sum(int u)
    {
        int ret = 0;
        while(u > 0)
        {
            ret += tree[u];
            u &= (u-1);
        }
        return ret;
    }
 
    void add(int u, int val)
    {
        while(u < tree.size())
        {
            tree[u] += val;
            u += (u & -u);
        }
    }
};
 
void init()
{
    cin >> N;
    aidx = N+1;
    for(int i = 1; i<=N; ++i)
        cin >> arr[i], first.push(arr[i]);
    cin >> M;
    int flag, x, y;
    for(int i =0; i<M; ++i)
    {
        cin >> flag;
        if(flag == 1)
        {
            cin >> x;
            arr[aidx++] = x;
            q.push(make_pair(flag, make_pair(x, -1)));
        }
        else
        {
            cin >> x >> y;
            q.push(make_pair(flag, make_pair(x, y)));
        }
    }
    sort(arr + 1, arr+aidx);
}
 
int getIdx(int u, bool head)
{
    int idx = lower_bound(arr+1, arr+aidx, u) - arr;
    if(head)
    {
        if(arr[idx] == u)
            return idx;
        else return idx - 1;
    }
    else
        return idx - 1;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    FenwickTree fwt(aidx);
    while(!first.empty())
        fwt.add(getIdx(first.front(), true), 1), first.pop();
 
    int x, y;
    while(!q.empty())
    {
        int flag = q.front().first;
        if(flag == 1)
        {
            x = q.front().second.first;
            fwt.add(getIdx(x, true), 1);
        }
        else
        {
            x = q.front().second.first;
            y = q.front().second.second;
            cout << y - x + 1 - fwt.sum(getIdx(y, true)) + fwt.sum(getIdx(x, false)) << "\n";
        }
        q.pop();
    }
}

 

 

 

 

 

 

 

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

15816번: 퀘스트 중인 모험가

 

 

 

 

 

 

퀘스트 중인 모험가

아주 큰 범위에 대한 펜윅트리 문제입니다.

-10억~10억 까지의 범위임으로 모든 구역을 다 배열로 잡는것이 사실상 불가능 합니다.

이때 '좌표 압축' 이라는 기법을 이용할수 있습니다.

마치 그래프에서 인접배열이 아닌 인접리스트를 사용하는것과 비슷한 느낌입니다.

구간내 모든 숫자를 가지고 있는것이 아니라, 문제에 필요한 숫자들

즉, input으로 들어오는 숫자들만 리스트로 가지고 있고, 

c++에서 제공하는 lower_bound함수를 이용해 내가 찾는 숫자의 index를 구해주어 펜윅트리를 사용하면 됩니다.

 

위의 문제에서는 또 vector의 push_back을 사용하니 시간초과가 나서 input이 최대로 들어왔을때의 크기만큼 배열을 미리 선언하고 배열의 top을 변수로 따로 저장하는 방법을 사용했씁니다.

 

 

 

 

 

 

3등 박제 ^0^