test/yosupo/staticrmq.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• Disjoint Sparse Table (data-structure/disjoint_sparse_table.hpp)

Code

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

#include <bits/stdc++.h>

#include "../../data-structure/disjoint_sparse_table.hpp"
using namespace std;

struct MinMonoid {
    using T = int;
    static T id() { return (1u << 31) - 1; }
    static T op(T a, T b) { return min(a, b); }
};

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

    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    DisjointSparseTable<MinMonoid> st(a);
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        cout << st.fold(l, r) << "\n";
    }
}

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

#include <bits/stdc++.h>

#line 3 "data-structure/disjoint_sparse_table.hpp"
#include <bit>
#line 5 "data-structure/disjoint_sparse_table.hpp"

template <typename M>
class DisjointSparseTable {
    using T = M::T;

   public:
    DisjointSparseTable() = default;
    explicit DisjointSparseTable(const std::vector<T>& v) {
        const int n = v.size();
        const int b = std::bit_width((unsigned int)n);
        lookup.resize(b + 1, std::vector<T>(n));
        std::ranges::copy(v, lookup[0].begin());
        for (int i = 1; i <= b; ++i) {
            int len = 1 << i;
            for (int l = 0; l + len / 2 < n; l += len) {
                int m = l + len / 2;
                lookup[i][m - 1] = v[m - 1];
                for (int j = m - 2; j >= l; --j) {
                    lookup[i][j] = M::op(lookup[i][j + 1], v[j]);
                }
                lookup[i][m] = v[m];
                for (int j = m + 1; j < std::min(l + len, n); ++j) {
                    lookup[i][j] = M::op(lookup[i][j - 1], v[j]);
                }
            }
        }
    }

    T fold(int l, int r) const {
        if (l == r) return M::id();
        if (r - l == 1) return lookup[0][l];
        int i = std::bit_width((unsigned int)(l ^ (r - 1)));
        return M::op(lookup[i][l], lookup[i][r - 1]);
    }

   private:
    std::vector<std::vector<T>> lookup;
};
#line 6 "test/yosupo/staticrmq.test.cpp"
using namespace std;

struct MinMonoid {
    using T = int;
    static T id() { return (1u << 31) - 1; }
    static T op(T a, T b) { return min(a, b); }
};

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

    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    DisjointSparseTable<MinMonoid> st(a);
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        cout << st.fold(l, r) << "\n";
    }
}

Back to top page