verify/verify-yosupo-ds/yosupo-sparse-table.test.cpp

• View this file on GitHub
• Last update: 2025-03-22 09:26:13+08:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• src/alfred/config/io-sync-off.hpp
• src/alfred/data_structure/sparse-table.hpp

Code

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

#include "../../src/alfred/config/io-sync-off.hpp"
#include "../../src/alfred/data_structure/sparse-table.hpp"
#include <iostream>

int n, q, l, r;

int main(int argc, char const *argv[]) {
    optimizeIO(), std::cin >> n >> q;

    std::vector<int> a(n);
    for (auto &x : a) std::cin >> x;

    SparseTable<MinInfo<int>> ST(a);

    while (q--) {
        std::cin >> l >> r;
        std::cout << ST.query(l, r - 1).val << '\n';
    }

    return 0;
}

#line 1 "verify/verify-yosupo-ds/yosupo-sparse-table.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>

inline void optimizeIO(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 1 "src/alfred/data_structure/sparse-table.hpp"



#line 7 "src/alfred/data_structure/sparse-table.hpp"

template <class T>
struct MaxInfo {
    T val;
    MaxInfo(void) { val = std::numeric_limits<T>::min(); }
    template <class InitT>
    MaxInfo(InitT x) { val = x; }
    MaxInfo operator+(MaxInfo &x) {
        return {std::max(val, x.val)};
    }
};
template <class T>
struct MinInfo {
    T val;
    MinInfo(void) { val = std::numeric_limits<T>::max(); }
    template <class InitT>
    MinInfo(InitT x) { val = x; }
    MinInfo operator+(MinInfo &x) {
        return {std::min(val, x.val)};
    }
};
template <class T>
struct GcdInfo {
    T val;
    GcdInfo(void) { val = T(); }
    template <class InitT>
    GcdInfo(InitT x) { val = x; }
    GcdInfo operator+(GcdInfo &x) {
#if __cplusplus >= 201703L
        return {std::gcd(x.val, val)};
#else
        return {__gcd(x.val, val)};
#endif
    }
};
template <class T>
class SparseTable {
private:
    int n;
    std::vector<std::vector<T>> ST;

public:
    SparseTable(void) {}
    SparseTable(int N) : n(N), ST(N, std::vector<T>(std::__lg(N) + 1)) {}
    template <class InitT>
    SparseTable(std::vector<InitT> &_init) : SparseTable(_init.size()) { init(_init, true); }
    template <class InitT>
    inline void init(std::vector<InitT> &_init, bool internal = false) {
        if (!internal) {
            n = _init.size();
            ST.assign(n, std::vector<T>(std::__lg(n) + 1));
        }
        for (int i = 0; i < n; i++) ST[i][0] = T(_init[i]);
        for (int i = 1; (1 << i) <= n; i++) {
            for (int j = 0; j + (1 << i) - 1 < n; j++) {
                ST[j][i] = ST[j][i - 1] + ST[j + (1 << (i - 1))][i - 1];
            }
        }
    }
    inline T query(int l, int r) { // 0 based
        if (l > r) return T();
        int w = std::__lg(r - l + 1);
        return ST[l][w] + ST[r - (1 << w) + 1][w];
    }
    inline T disjoint_query(int l, int r) {
        if (l > r) return T();
        T ans = T();
        for (int i = std::__lg(r - l + 1); i >= 0; i--) {
            if ((1 << i) <= r - l + 1) {
                ans = ans + ST[l][i];
                l += 1 << i;
            }
        }
        return ans;
    }
};


#line 6 "verify/verify-yosupo-ds/yosupo-sparse-table.test.cpp"

int n, q, l, r;

int main(int argc, char const *argv[]) {
    optimizeIO(), std::cin >> n >> q;

    std::vector<int> a(n);
    for (auto &x : a) std::cin >> x;

    SparseTable<MinInfo<int>> ST(a);

    while (q--) {
        std::cin >> l >> r;
        std::cout << ST.query(l, r - 1).val << '\n';
    }

    return 0;
}

Back to top page