[트리] MORDOR 등산로

1. 문제

 

표지판번호가  0 ~ n-1  인 표지판이 있는  등산로가 있다고한다.

 

표지판에는 해발고도가 적혀있고 배열 h에 번호마다 해발고도가 저장되어있다.

 

a번 표지판에서 b번 표지판까지의 등산로의 난이도를 a~b의 최대 해발고도와  최소 해발고도의 차이라고 한다.

 

a, b가 주어졌을때 난이도를 구하는 함수를 만드라는게 이 문제의 의도이다.

 

2. 구간 트리 초기화

 

pair 객체를 가지는 구간 트리를 만들어서 각 구간마다 최대 최소인 원소를 저장해야한다.

 

이는 바텀업 방식으로 재귀를 이용하여 리프부터 루트까지 각 노드를 채워야한다.

 

기저조건으로 구간의 길이가 1 일때(리프) 구간은 최대와 최소가 같은 pair을 반환한다.

 

재귀를 이용하여 왼쪽, 오른쪽 서브트리를 루트로 합친다.

 

합칠때 최대는 최대끼리 최소는 최소끼리 비교하여 루트에 저장한다.

 

3. 구간 트리 질의 연산 구현

 

구간에 포함되지 않으면 (-1 ,-1) 쌍을 반환하여, 무시하도록 한다.

구간에 포함되면 해당 노드의 쌍을 반환한다.

 

구간을 넘어서게 되면 오른쪽, 왼쪽으로 나누어 문제를 해결한다.

 

 

4. 책에서의 풀이

 

RMQ를 이용하여 최소값을 구한뒤, 

높이 배열에 -1을 곱하여 RMQ로 최대값을 쉽게 구할 수 있다.

 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
 
using namespace std;
 
int testCase;
 
pair<int, int> selectMinMax(const pair<int, int>& a, const pair<int, int>& b) {
    if(a.first == -1) return b;
    if(b.first == -1) return a;
    int min = a.first < b.first ? a.first: b.first;
    int max = a.second > b.second ? a.second: b.second;
    return make_pair(min, max);
}
 
struct milestone {
    vector<pair<int, int> > tree;
    int stoneN;
    milestone(const vector<int>& stone) {
        stoneN = stone.size();
        tree.resize(stoneN*4);
        init(stone, 0 ,0, stoneN);
    } 
    pair<int, int> init(const vector<int>& stone, int node,int lo, int hi) {
        int mid = (lo+hi)/2;
        if(lo + 1 == hi) return tree[node] = make_pair(stone[lo], stone[lo]);
        return tree[node] = selectMinMax(init(stone, node*2 + 1, lo, mid), init(stone, node*2 + 2, mid, hi));
    }
    pair<int, int> query(int node , int lo, int hi, int nlo, int nhi) {
        if(nhi <= lo || hi < nlo) return make_pair(-1, -1);
        if(lo<= nlo && nhi <= hi+1) return tree[node];
        int mid = (nlo+nhi)/2;
 
        return selectMinMax(query(node*2+1, lo, hi, nlo, mid), query(node*2 + 2, lo, hi, mid, nhi));
    }
    int query(int lo, int hi) {
        pair<int, int> ret = query(0, lo, hi, 0, stoneN);
        return ret.second - ret.first;
    }
};
 
int main() {
    cin>>testCase;
    while(testCase--)
    {
        int N, q, a, b;
        cin>>N>>q;
        vector<int> h;
        while(N--) 
        {
            scanf("%d",&a);
            h.push_back(a);
        }
        milestone tree(h);
        while(q--)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n", tree.query(a,b));
        }
    }
}

 

 

• MORDOR

 

 

 

- 알고리즘 문제해결전략 747p