cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: segmenttree/test/point-update-range-min.test.cpp

Depends on

Code

#include "../range_minimum_query.hpp"
#include <iostream>
using namespace std;
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A"

int main() {
    int N, Q;
    cin >> N >> Q;
    RangeMinimumQuery<int, (1LL << 31) - 1> rmq(N);
    for (int q = 0; q < Q; q++) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0) {
            rmq.update(x, y);
        } else {
            cout << rmq.get(x, y + 1) << '\n';
        }
    }
}
#line 2 "segmenttree/range_minimum_query.hpp"
#include <iostream>
#include <limits>
#include <vector>

// CUT begin
// Range Minimum Query
// - RangeMinimumQuery<T, defaultT>(int N = 0) : Initialize array x = [defaultT, ..., defaultT] of
// length N, O(N)
// - RangeMinimumQuery<T, defaultT>(const std::vector<T> &vals) : Initialize array x by [vals[0],
// ..., vals[-1]], O(N)
// - update(int pos, T val) : x[pos] <- val, O(log N)
// - get(int begin, int end) : Get min(x_begin, ..., x_(end - 1)), O(log N)
template <typename T, T defaultT = std::numeric_limits<T>::max() / 2> struct RangeMinimumQuery {
    int N;
    int head;
    std::vector<T> x;
    T _get(int begin, int end, int pos, int l, int r) const {
        if (r <= begin or l >= end) return defaultT;
        if (l >= begin and r <= end) return x[pos];
        return std::min(_get(begin, end, 2 * pos + 1, l, (l + r) / 2),
                        _get(begin, end, 2 * pos + 2, (l + r) / 2, r));
    }
    RangeMinimumQuery(int N = 0) : N(N) {
        int N_tmp = 1;
        while (N_tmp < N) N_tmp <<= 1;
        x.assign(N_tmp * 2, defaultT), head = N_tmp - 1;
    }
    void _build(const std::vector<T> &vals) {
        std::copy(vals.begin(), vals.end(), x.begin() + head);
        for (int i = head - 1; i >= 0; i--) x[i] = std::min(x[i * 2 + 1], x[i * 2 + 2]);
    }
    RangeMinimumQuery(const std::vector<T> &vals) : N(vals.size()) {
        int N_tmp = 1;
        while (N_tmp < N) N_tmp <<= 1;
        x.assign(N_tmp * 2, defaultT), head = N_tmp - 1;
        _build(vals);
    }
    void update(int pos, T val) {
        pos += head, x[pos] = val;
        while (pos) pos = (pos - 1) / 2, x[pos] = std::min(x[pos * 2 + 1], x[pos * 2 + 2]);
    }
    T get(int begin, int end) const { return _get(begin, end, 0, 0, (int)x.size() / 2); }
    friend std::ostream &operator<<(std::ostream &os, const RangeMinimumQuery &s) {
        os << '[';
        for (int i = 0; i < s.N; i++) os << s.get(i, i + 1) << ',';
        return os << ']';
    }
};
#line 3 "segmenttree/test/point-update-range-min.test.cpp"
using namespace std;
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A"

int main() {
    int N, Q;
    cin >> N >> Q;
    RangeMinimumQuery<int, (1LL << 31) - 1> rmq(N);
    for (int q = 0; q < Q; q++) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0) {
            rmq.update(x, y);
        } else {
            cout << rmq.get(x, y + 1) << '\n';
        }
    }
}
Back to top page