BOJ 13537 수열과 쿼리 1 (오프 라인 쿼리 version)

이 문제는 이미 persistent segment tree를 이용하여 해결한 바 있다.

 

코드가 짧아서 그랬는데 그 방식만 기록해 두자니 찜찜해서 오프 라인 쿼리로 해결하는 것도 적어 둔다. (당연히 오프 라인 쿼리 쪽이 압도적으로 빠르다.)

 

문제를 이해하기 쉬운 방식으로 재구성해보자.

어떤 학급의 학생들에게 이름순으로 일련 번호(index)를 매겼다고 가정한다.

여기서 학생들의 키(value)에 관한 정보를 얻고 싶다.

 

처음에  \( [l_1, r_1]\) 번 사이의 학생 중에서 키가 175cm 이 넘는 사람은 몇 명인가를 묻고

다음에 \( [l_2, r_2]\) 번에서 180cm 이상인 사람이 몇 명이지를 물었다고 하자.

 

 

이런 식으로 질문이 계속될 때,

만약 키에 관한 segment tree를 구성했다면

특정 번호에 해당되는 학생들에 관한 정보를 segment tree 에 집어넣을 수 없으니

이름순의 구간에 관한 정보를 구하기가 힘든다.

 

persistent segment tree 같은 것을 이용하여 입력순(이름순)의 정보를 같이 고려할 수는 있지만 오버헤드가 너무 크다.

 

개선할 여지가 없을까?

 

일련 번호(입력순의 index)와 키(value)라는 순서를 줄 수 있는 두 정보를 바꿔서 생각하자.  (다른 글에서 짧게 언급한 것처럼 키순이냐 이름순이냐의 문제는 편의에 따르면 된다.)

 

키를 이용해서 정렬하여 180cm 이상인 학생들에게 자신의 번호를 일련 번호 빈칸에 기입하게 하자.

그리고 구간 쿼리를 이용하여  \( [l_2, r_2]\) 범위에 학생 수를 센다.

 

다음으로 175cm 이상으로 180cm 미만인 학생들에게 자기 번호를 기재하게 한 다음,

구간 쿼리를 이용하여 \( [l_1, r_1]\) 범위의 학생 수를 센다.

이미 180cm 이상인 학생들은 기재되어 있고 175cm 이상이라는 조건에도 부합되니 아무 문제가 없다.

 

 

본래 segment tree는 전체의 정보를 구간들을 나누어 분산해서 저장함으로써

구간에 대한 질문에 효과적으로 대답하기 위한 장치다.

 

정렬가능한 여러 정보가 있을 때, 어떤 정보를 기준으로 사고하는 것이 유리한지만 생각해 본다면

이런 문제들은 어렵지 않게 해결된다.

 

#include<bits/stdc++.h>

using namespace std;

pair<int,int> arr[100001];
int sz=1, tree[1<<18];

struct query {
    int l, r, k, idx;  
    bool operator<(const query &rhs) const{
        return k > rhs.k;    
    }
} q[100001];

int ans[100001];

void upd(int p){
    p += sz;   
    for (; p>0; p>>=1)
        tree[p]++;
}

int qry(int l, int r){
    int cnt = 0;
    l += sz, r += sz;
    
    for (; l<=r; l>>=1, r>>=1){
        if (l & 1) cnt += tree[l++];
        if (~r & 1) cnt += tree[r--];
    }
    return cnt;
}

int main(){
    int N, M;
    scanf("%d", &N);
    for(;sz<N;sz<<=1);
    
    for (int i = 0; i < N; ++i){
        int t; scanf("%d", &t);
        arr[i].first=t;
        arr[i].second = i;
    }
    sort(arr, arr+N);
    
    scanf("%d",&M);
    for (int i = 0; i < M; ++i){
        int l,r,k; scanf("%d%d%d",&l,&r,&k);
        q[i].l =l, q[i].r =r, q[i].k=k;
        q[i].idx = i;
    }
    sort(q, q+M);
    
    int p, s = N;
    pair<int,int> tmp(0,INT_MAX);
    for (int i = 0; i < M; ++i) {
        tmp.first = q[i].k;
        p = upper_bound(arr, arr+s, tmp) - arr;
        for (int j = s-1; j >= p; --j)
            upd(arr[j].second);
        s = p;
        ans[q[i].idx] = qry(q[i].l-1, q[i].r-1);
    }
    for (int i = 0; i < M; ++i)
        printf("%d\n", ans[i]);
    return 0;
}