Verify/StaticRMQ.test.cpp

View this file on GitHub
Last update: 2023-02-11 22:28:05+08:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

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

#include "../DataStructure/RMQ.hpp"
#include "../Template/Template.hpp"

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

    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (auto&& it : a) std::cin >> it;
    RMQ<int> rmq(a);

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << rmq.rangeMin(l, r) << '\n';
    }

    return 0;
}

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

#line 2 "Template/Template.hpp"

#include <bits/stdc++.h>

using i64 = std::int64_t;
#line 3 "DataStructure/RMQ.hpp"

template <class T, class Cmp = std::less<T>>
struct RMQ {
    const int n;
    const Cmp cmp;
    std::vector<std::vector<T>> a;
    RMQ(const std::vector<T> &init) : n(init.size()), cmp(Cmp()) {
        int lg = std::__lg(n);
        a.assign(lg + 1, std::vector<T>(n));
        for (int j = 0; j <= lg; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                a[j][i] =
                    (j == 0 ? init[i]
                            : std::min(a[j - 1][i],
                                       a[j - 1][i + (1 << (j - 1))], cmp));
            }
        }
    }
    T rangeMin(int l, int r) {
        int k = std::__lg(r - l);
        return std::min(a[k][l], a[k][r - (1 << k)], cmp);
    }
};
#line 5 "Verify/StaticRMQ.test.cpp"

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

    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (auto&& it : a) std::cin >> it;
    RMQ<int> rmq(a);

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << rmq.rangeMin(l, r) << '\n';
    }

    return 0;
}