[BOJ] 백준 15816. 퀘스트 중인 모험가 (Platinum IV)

추천받은 문제 중 하나.

입력 범위가 상당히 크기 때문에 꽤나 어려워 보이지만, 오히려 그러한 점이 힌트가 되는 문제.

문제는 아래와 같다.

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

15816번: 퀘스트 중인 모험가

---

의식의 흐름 및 해설

수의 범위가 굉장히 크기 때문에 O(N^2) 이상의 시간복잡도 풀이는 불가능하며,

입력받는 퀘스트 범위가 -10억 ~ 10억인 점, 요청으로 추가되는 퀘스트 개수가 최대 M (<= 1e6)개인 점을 고려하면, 좌표압축을 생각해볼 수 있다.

 

퀘스트를 수행하지 않은 개수를 구해주는 문제이므로,

퀘스트를 수행한 개수의 합을 담아주는 자료구조인 세그먼트 트리를 이용해주도록 하자.

sum of segtree (합세그)이므로 펜윅트리를 이용할 수도 있겠다.

 

퀘스트를 수행하는 요청이 들어올 때마다 update를 해주면 되고,

2번 쿼리를 날릴 때, L, R의 범위가 상당히 크고, 퀘스트 개수는 최대 2e6개인 점을 생각하면, 좌표압축 및 이분탐색으로 L, R이 몇 번째 퀘스트 범위인지 찾아내는 작업으로 문제를 해결할 수 있겠다.

 

이렇게 하면 좌표압축으로 인해 시간복잡도가 O(MlgN)으로 충분히 돌아가게 된다.

다만, a*MlgN에서 a의 값이 꽤 크고, 수의 범위가 2e6으로 커서 메모리도 많이 잡아먹기 때문에 예상보다 시간, 메모리가 더 나오는 것을 확인할 수 있다.

 

내 코드 구현 상, 펜윅 트리는 1-index에서만 적용되는 점,

수의 범위 최대가 1e6이 아닌, 1번 쿼리 M개 추가 가능성을 고려하여 2e6으로 둬야 하는 점들을 놓쳐

3번의 맞왜틀을 받았다.

---

코드

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int,pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 2e6+7;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int N,Q,a[MAX],tree[MAX];
vector<int> v;
vector<pi> q;
int query(int i){
    int ret=0;
    for(;i;i-=i&-i){
        ret+=tree[i];
    }
    return ret;
}
void update(int i,int val){
    for(;i<=N;i+=i&-i){
        tree[i]+=val;
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>a[i];
        v.push_back(a[i]);
    }
    cin>>Q;
    int initN=N;
    while(Q--){
        int ch,L,R;
        cin>>ch>>L;
        if(ch==1){
            v.push_back(L);
            q.push_back({L,INF});
            ++N;
        }
        else{
            cin>>R;
            q.push_back({L,R});
        }
    }
    sort(all(v));
    for(int i=0;i<initN;i++){
        int n=lower_bound(all(v), a[i])-v.begin()+1;
        update(n,1);
    }
    for(pi i:q){
        if(i.second==INF){
            int n=lower_bound(all(v), i.first)-v.begin()+1;
            update(n,1);
        }
        else{
            int cnt=i.second-i.first+1;
            int left=lower_bound(all(v),i.first)-v.begin()+1;
            int right=upper_bound(all(v),i.second)-v.begin()+1;
            cout<<cnt-(query(right-1)-query(left-1))<<"\n";
        }
    }
}

---

쿼리로 N 개수가 추가되어 MAX 범위가 늘어난다는 점을 간과했다.

이렇게 될 경우, fenwick tree 범위도 어긋나기 때문에 항상 조심해주도록 하자.

 

오랜만에 좌표압축 + 펜윅트리를 사용하며 복습하게 해준 재밌는 문제를 풀었다.