verify/ds/sparse_table.test.cpp

View this file on GitHub
Last update: 2024-12-10 21:37:51-05:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include "algo/common.h"

/* #include */
#include "algo/ds/sparse_table.h"

using namespace std;
using namespace algo;
using ds::sparse_table;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sparse_table st(a);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << st.query(l, r - 1) << '\n';
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}

#line 1 "verify/ds/sparse_table.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 2 "algo/common.h"
#ifndef PREPROCESS
#include <bits/stdc++.h>
#endif

namespace algo {}

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#line 3 "verify/ds/sparse_table.test.cpp"

/* #include */
#line 3 "algo/ds/common.h"

namespace algo::ds {

template <typename T>
T min(const T &a, const T &b) {
    return std::min(a, b);
}

}; // namespace algo::ds
#line 3 "algo/utils/bits.h"

namespace algo::utils {

// Returns number of set bits in x
constexpr int popcnt(int64_t x) {
    return __builtin_popcountll(x);
}
// Returns floor(log_2(x))
constexpr int lg2(uint64_t x) {
    return std::bit_width(x) - 1;
}

} // namespace algo::utils
#line 5 "algo/ds/sparse_table.h"

namespace algo::ds {

template <typename T>
struct sparse_table {
    // Must be constructed with idempotent function. Call init() after if using
    // this constructor.
    sparse_table(int _n, const std::function<T(T, T)> &op = min<T>)
        : n(_n), k(utils::lg2(n)), op(op), st(k + 1, std::vector<T>(n)) {
    }
    // Must be constructed with idempotent function
    sparse_table(const std::vector<T> &a,
                 const std::function<T(T, T)> &op = min<T>)
        : sparse_table(sz(a), op) {
        init(a);
    }
    void init(const std::vector<T> &a) {
        assert(sz(a) <= n);
        std::copy(all(a), st[0].begin());
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                st[i][j] = op(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    // Queries on [l, r]
    T query(int l, int r) {
        int i = utils::lg2(r - l + 1);
        return op(st[i][l], st[i][r - (1 << i) + 1]);
    }
    friend std::ostream &operator<<(std::ostream &os, const sparse_table &t) {
        return os << t.st[0];
    }

private:
    int n, k;
    std::function<T(T, T)> op;
    std::vector<std::vector<T>> st;
};

} // namespace algo::ds
#line 6 "verify/ds/sparse_table.test.cpp"

using namespace std;
using namespace algo;
using ds::sparse_table;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sparse_table st(a);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << st.query(l, r - 1) << '\n';
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	6 ms	3 MB
g++	max_random_00	AC	164 ms	44 MB
g++	max_random_01	AC	171 ms	44 MB
g++	max_random_02	AC	164 ms	44 MB
g++	max_random_03	AC	178 ms	44 MB
g++	max_random_04	AC	162 ms	44 MB
g++	random_00	AC	136 ms	35 MB
g++	random_01	AC	146 ms	41 MB
g++	random_02	AC	76 ms	7 MB
g++	random_03	AC	74 ms	38 MB
g++	random_04	AC	62 ms	26 MB
g++	small_00	AC	6 ms	3 MB
g++	small_01	AC	6 ms	3 MB
g++	small_02	AC	6 ms	3 MB
g++	small_03	AC	6 ms	3 MB
g++	small_04	AC	6 ms	3 MB
g++	small_05	AC	5 ms	3 MB
g++	small_06	AC	6 ms	3 MB
g++	small_07	AC	6 ms	3 MB
g++	small_08	AC	6 ms	3 MB
g++	small_09	AC	6 ms	3 MB
g++	small_values_00	AC	151 ms	44 MB
g++	small_width_query_00	AC	189 ms	44 MB
g++	small_width_query_01	AC	189 ms	44 MB
g++	small_width_query_02	AC	186 ms	44 MB
g++	small_width_query_03	AC	177 ms	44 MB
g++	small_width_query_04	AC	182 ms	44 MB