test/yosupo/static_rmq.test.cpp

View this file on GitHub
Last update: 2022-09-01 14:18:35+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <iostream>
#include <limits>

#include "../../data_type/min_monoid.hpp"
#include "../../sparse_table/sparse_table.hpp"
using namespace std;
using llong = long long;

llong n, q;
vector<llong> a;

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto &v : a) cin >> v;

    SparseTable<MinMonoid<llong>> rmq(a.begin(), a.end());

    while (q--) {
        llong l, r;
        cin >> l >> r;
        cout << rmq.fold(l, r) << '\n';
    }

    return 0;
}

#line 1 "test/yosupo/static_rmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <iostream>
#include <limits>

#line 1 "data_type/min_monoid.hpp"



#include <algorithm>
#line 6 "data_type/min_monoid.hpp"
#include <numeric>

//===
template <class T>
struct MinMonoid {
    using value_type = T;
    inline static T identity() {
        return std::numeric_limits<T>::max();
    };
    inline static T operation(const T a, const T b) {
        return std::min(a, b);
    };
};
//===


#line 1 "sparse_table/sparse_table.hpp"



#include <functional>
#include <iterator>
#include <vector>

//===
template <class SemiLattice>
struct SparseTable {
    using S = SemiLattice;
    using T = typename SemiLattice::value_type;

    std::vector<std::vector<T>> table;
    std::vector<size_t> log2;

    SparseTable() = default;

    template <class InputItr>
    SparseTable(InputItr first, InputItr last) {
        int n = std::distance(first, last);
        log2.assign(n + 1, 0);
        for (int i = 2; i <= n; i++) log2[i] = log2[i / 2] + 1;

        table.reserve(log2[n] + 1);
        table.emplace_back(first, last);

        for (int i = 1; (1 << i) <= n; i++) {
            int w = 1 << (i - 1);
            table.emplace_back();
            table.back().reserve(n - (1 << i) + 1);
            for (int j = 0; j + (1 << i) <= n; j++) {
                table[i].emplace_back(
                    S::operation(table[i - 1][j], table[i - 1][j + w]));
            }
        }
    };

    //[l, r)
    T fold(int l, int r) {
        int k = log2[r - l];
        return S::operation(table[k][l], table[k][r - (1 << k)]);
    };

    int size() {
        return table[0].size();
    };

    T operator[](const int k) {
        return table[0][k];
    };
};
//===


#line 8 "test/yosupo/static_rmq.test.cpp"
using namespace std;
using llong = long long;

llong n, q;
vector<llong> a;

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto &v : a) cin >> v;

    SparseTable<MinMonoid<llong>> rmq(a.begin(), a.end());

    while (q--) {
        llong l, r;
        cin >> l >> r;
        cout << rmq.fold(l, r) << '\n';
    }

    return 0;
}