PKU JudgeOnline 3264 - Balanced Lineup

問題

http://poj.org/problem?id=3264

頭の牛が整列していて, 牛たちにはそれぞれ番号と身長が与えられています.
ここである区間の牛たちにおいて最高の身長と最低の身長の差を求めたいです. そのようなクエリが個与えられるので, それぞれのクエリについて答えてください.

解法

Segment Treeを使ってRMQを実装しました. Segment Treeを2つ用意し, 一方には通常通りの身長を, 他方には負の値に反転させた身長を入れます. こうすることでRMQの実装を使いまわすことができます.

ソースコード

#include <vector>
#include <iostream>
#include <climits>
using namespace std;

template<typename T>
struct SegmentTree {
    int n;
    vector<T> elt;

    SegmentTree() {}
    SegmentTree(int n_) {
        // 簡単のため, 要素数を2の冪乗に
        n = 1;
        while (n < n_) n *= 2;
        // 要素の初期化
        elt = vector<T>(2 * n - 1);
        for (int i = 0; i < 2 * n - 1; i++) {
            elt[i] = INT_MAX;
        }
    }

    void update(int k, T a) {
        k += n - 1;
        elt[k] = a;
        // 登りながら更新
        while (k > 0) {
            k = (k - 1) / 2;
            elt[k] = min(elt[k * 2 + 1], elt[k * 2 + 2]);
        }
    }

    T query(int a, int b, int v_id, int v_lb, int v_ub) {
        if (v_ub <= a || b <= v_lb) return INT_MAX;

        if (a <= v_lb && v_ub <= b) return elt[v_id];
        else {
            T ql = query(a, b, v_id * 2 + 1, v_lb, (v_lb + v_ub) / 2);
            T qr = query(a, b, v_id * 2 + 2, (v_lb + v_ub) / 2, v_ub);
            return min(ql, qr);
        }
    }
};

const int kMAX_N = 50010;
const int kMAX_Q = 200010;

int N, Q;
int height[kMAX_N];
int A[kMAX_Q], B[kMAX_Q];

void Solve() {
    SegmentTree<int> max_tree(N),   // 値を負にして入れる 
                     min_tree(N);   // 値をそのまま入れる
    for (int i = 0; i < N; i++) {
        max_tree.update(i, -height[i]);
        min_tree.update(i, height[i]);
    }
    for (int i = 0; i < Q; i++) {
        int neg_max = max_tree.query(A[i] - 1, B[i], 0, 0, max_tree.n),
            max_h = -neg_max,
            min_h = min_tree.query(A[i] - 1, B[i], 0, 0, min_tree.n);
        cout << max_h - min_h << endl;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> Q;

    for (int i = 0; i < N; i++) {
        cin >> height[i];
    }

    for (int i = 0; i < Q; i++) {
        cin >> A[i] >> B[i];
    }

    Solve();
    return 0;
}

感想

Segment Tree好き