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/sqrt_tree.hpp" using namespace std; struct MinSemigroup { using T = int; 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 (auto& x : a) cin >> x; SqrtTree<MinSemigroup> st(a); while (Q--) { int l, r; cin >> l >> r; cout << st.fold(l, r) << "\n"; } }
#line 1 "test/yosupo/staticrmq.sqrt_tree.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include <bits/stdc++.h> #line 3 "data-structure/sqrt_tree.hpp" #include <bit> #line 5 "data-structure/sqrt_tree.hpp" template <typename S> class SqrtTree { using T = S::T; public: SqrtTree() = default; explicit SqrtTree(const std::vector<T>& v) : v(v) { const int n = v.size(), lg = std::bit_width((unsigned int)n); on_layer.resize(lg + 1); int n_layer = 0; for (int i = lg; i > 1; i = (i + 1) / 2) { on_layer[i] = n_layer++; layer_lg.push_back(i); } for (int i = lg - 1; i >= 0; --i) on_layer[i] = std::max(on_layer[i], on_layer[i + 1]); pref.resize(n_layer, std::vector<T>(n)); suf.resize(n_layer, std::vector<T>(n)); btwn.resize(n_layer, std::vector<T>(1 << lg)); for (int layer = 0; layer < n_layer; ++layer) { int prev_b_sz = 1 << layer_lg[layer]; int b_sz = 1 << ((layer_lg[layer] + 1) / 2); int b_cnt = 1 << (layer_lg[layer] / 2); for (int l = 0; l < n; l += prev_b_sz) { int r = std::min(l + prev_b_sz, n); // calculate pref and suf for (int a = l; a < r; a += b_sz) { int b = std::min(a + b_sz, r); pref[layer][a] = v[a]; for (int i = a + 1; i < b; ++i) { pref[layer][i] = S::op(pref[layer][i - 1], v[i]); } suf[layer][b - 1] = v[b - 1]; for (int i = b - 2; i >= a; --i) { suf[layer][i] = S::op(v[i], suf[layer][i + 1]); } } // calculate btwn for (int i = 0; i < b_cnt; ++i) { T val = suf[layer][l + i * b_sz]; btwn[layer][l + i * b_cnt + i] = val; for (int j = i + 1; j < b_cnt; ++j) { val = S::op(val, suf[layer][l + j * b_sz]); btwn[layer][l + i * b_cnt + j] = val; } } } } } T fold(int l, int r) const { --r; if (l == r) return v[l]; if (l + 1 == r) return S::op(v[l], v[r]); int layer = on_layer[std::bit_width((unsigned int)(l ^ r))]; int b_sz = 1 << ((layer_lg[layer] + 1) / 2); int b_cnt = 1 << (layer_lg[layer] / 2); int a = (l >> layer_lg[layer]) << layer_lg[layer]; int lblock = (l - a) / b_sz + 1; int rblock = (r - a) / b_sz - 1; T val = suf[layer][l]; if (lblock <= rblock) val = S::op(val, btwn[layer][a + lblock * b_cnt + rblock]); val = S::op(val, pref[layer][r]); return val; } private: std::vector<int> layer_lg, on_layer; std::vector<T> v; std::vector<std::vector<T>> pref, suf, btwn; }; #line 6 "test/yosupo/staticrmq.sqrt_tree.test.cpp" using namespace std; struct MinSemigroup { using T = int; 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 (auto& x : a) cin >> x; SqrtTree<MinSemigroup> st(a); while (Q--) { int l, r; cin >> l >> r; cout << st.fold(l, r) << "\n"; } }