sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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"; } }