test/segment_tree.aoj.DSL_2_A.test.cpp

• View this file on GitHub
• Last update: 2020-05-11 17:18:45+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_A

Depends on

• lib/segment_tree.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_A"

#include <iostream>
#include "../lib/segment_tree.hpp"

int main() {
    int n, q; std::cin >> n >> q;
    auto op = [](long long a, long long b) { return std::min(a, b); };
    SegmentTree<long long>
        seg(std::vector<long long>(n, (1LL << 31) - 1),
            op, (1LL << 31) - 1);
    for (int i = 0; i < q; i++) {
        int com, x, y; std::cin >> com >> x >> y;
        if (com) std::cout << seg.getval(x, y + 1) << std::endl;
        else seg.update(x, y);
    }
    return 0;
}

#line 1 "test/segment_tree.aoj.DSL_2_A.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_A"

#include <iostream>
#line 1 "lib/segment_tree.hpp"



#include <vector>
#include <algorithm>
#include <functional>

template<typename Monoid>
class SegmentTree {
public:
    using Operator = std::function<Monoid(Monoid, Monoid)>;

    SegmentTree(int n, const Operator &op, const Monoid init)
        : op(op), init(init) {

        num = 1;
        while (num < n) num *= 2;
        dat.resize(2 * num, init);
    }

    SegmentTree(const std::vector<Monoid> &m,
        const Operator &op, const Monoid init)
        : SegmentTree(m.size(), op, init) {

        int n = m.size();
        for (int i = 0; i < n; i++) {
            dat[num - 1 + i] = m[i];
        }
        for (int i = num - 2; i >= 0; i--) {
            dat[i] = op(dat[2 * i + 1], dat[2 * i + 2]);
        }
    }

    // Update the k-th value (0-indexed) to a.
    void update(int k, Monoid a) {
        k += num - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = op(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }

    // Get the value of the range [a, b).
    // k: The index of the node.
    // [left, right): The range corresponds to the k-th node.
    // Call like getval(a, b).
    Monoid getval(int a, int b, int k = 0, int left = 0, int right = -1) {
        if (right < 0) right = num;
        if (right <= a || b <= left) return init;
        if (a <= left && right <= b) return dat[k];
        Monoid vleft = getval(
            a, b, 2 * k + 1, left, left + (right - left) / 2);
        Monoid vright = getval(
            a, b, 2 * k + 2, left + (right - left) / 2, right);
        return op(vleft, vright);
    }

private:
    int num;
    std::vector<Monoid> dat;
    const Operator op;
    const Monoid init;
};

// Example: Range-Minimum Point-Update Segment Tree
SegmentTree<int> make_rmpu_segment_tree(const std::vector<int> &init) {
    const int INF = 1e9 + 2;
    auto op = [](int a, int b) { return std::min(a, b); };
    return SegmentTree<int>(init, op, INF);
}


#line 5 "test/segment_tree.aoj.DSL_2_A.test.cpp"

int main() {
    int n, q; std::cin >> n >> q;
    auto op = [](long long a, long long b) { return std::min(a, b); };
    SegmentTree<long long>
        seg(std::vector<long long>(n, (1LL << 31) - 1),
            op, (1LL << 31) - 1);
    for (int i = 0; i < q; i++) {
        int com, x, y; std::cin >> com >> x >> y;
        if (com) std::cout << seg.getval(x, y + 1) << std::endl;
        else seg.update(x, y);
    }
    return 0;
}

Back to top page