[백준 15816번] [세그먼트 트리] 퀘스트 중인 모험가

Approach

특정한 구간에 대한 정보를 묻고 있는 상황이므로 세그먼트 트리 자료구조를 활용할 수 있지 않을까라고 판단해주면 된다.

이때, 퀘스트가 총 21억개로 상당히 많은 것과 달리 처리한 퀘스트는 최대 2백만정도 밖에 존재하지 않는다.

따라서 처리한 퀘스트를 기준으로 좌표압축을 해주고, 특정 쿼리에 대한 해결한 퀘스트의 개수를 구해주는 방식으로 이 문제를 해결할 수 있다.

 

단, 이런 방식으로 처리하려면 입력값으로 들어오는 좌표들을 미리 한번에 받아두어야하므로 미리 정보를 다 저장해둔다.

 

처음에 접근한 방식은 해결한 퀘스트 번호만을 가지고 좌표 압축을 진행하였다. 다만 이 방식의 문제점은, request에서 퀘스트 번호가 주어졌을 때 무엇을 포함하고 포함하지 않을 것인지에 대한 기준이 모호하다. 만약 해당하는 수가 없을 경우 좌표 압축된 해당 index보다 1 작은 것 까지의 쿼리를 구해야하고, 존재할 경우에는 포함시켜야 한다. 예외처리를 통해서 처리해줄 수 있기는 하지만 이분탐색을 하는 과정에서 상당히 복잡해진다.

 

따라서 그냥 일관되게 마지막에 처리하는 쿼리에 대한 좌표 값도 좌표압축시켜주면 조금 더 쉽게 구할 수 있다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define INF 1000000001

using namespace std;
int seg[12000008];
int req[1000002][2];
vector<int> s;

void update(int node_index, int node_left, int node_right, int update_index){
    if(update_index < node_left || update_index > node_right) return; // Out of bound
    
    // Base case
    if(node_left == node_right){
        seg[node_index]++;;
        return;
    }
    else{
        int mid = (node_left + node_right) / 2;
        update(node_index * 2, node_left, mid, update_index);
        update(node_index * 2 + 1, mid + 1, node_right, update_index);
        seg[node_index]++;
    }
}

int query(int node_index, int node_left, int node_right, int query_left, int query_right){
    // Out of bound
    if(query_right < node_left || node_right < query_left) return 0;
    // All satisfied
    else if(query_left <= node_left && query_right >= node_right) return seg[node_index];

    int mid = (node_left + node_right) / 2;
    return query(node_index * 2, node_left, mid, query_left, query_right) +
           query(node_index * 2 + 1, mid + 1, node_right, query_left, query_right);
}

int lower_bound_index(int num){
    return lower_bound(s.begin(), s.end(), num) - s.begin();
}

int main(void){
    fastio;
    memset(seg, 0, sizeof(seg));
    memset(req, 0, sizeof(req));
    
    int N, M;
    vector<int> input_value;
    
    // Input data 
    cin >> N;
    for(int i = 0; i < N; i++){
        int t;
        cin >> t;
        s.push_back(t);
        input_value.push_back(t);
    }

    // Request
    cin >> M;
    for(int i = 0; i < M; i++){
        int q;
        cin >> q;
        // Update seg
        if(q == 1){
            int u;
            cin >> u;
            s.push_back(u);
            req[i][0] = u;
            req[i][1] = INF;
        }
        // Request current query value (Storing query)
        else{
            int v1, v2;
            cin >> v1 >> v2;
            s.push_back(v1);
            s.push_back(v2);
            req[i][0] = v1;
            req[i][1] = v2;
        }
    }

    s.push_back(-INF); // 강제로 시작 index를 1로 만들어줌
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end()); // 겹치는거 지워줌

    int node_left = 1;
    int node_right = s.size() - 1;

    for(int i = 0; i < input_value.size(); i++){
        update(1, node_left, node_right, lower_bound_index(input_value[i]));
    }

    for(int i = 0; i < M; i++){
        // Request : 1
        if(req[i][1] == INF){
            update(1, node_left, node_right, lower_bound_index(req[i][0]));
        }
        else{
            int p_sum = query(1, node_left, node_right, lower_bound_index(req[i][0]), lower_bound_index(req[i][1]));
            cout << req[i][1] - req[i][0] + 1 - p_sum << "\n";
        }
    }

    return 0;
}