This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "data_structure/offline_dual_segtree_2d.hpp"
可換モノイドについて、長方形クエリ、 $1$ 点所得を行えるデータ構造。クエリ先読みにより、必要な部分だけ作ることでメモリ使用量を減らして点の座標が$10^9$とかでも使える。
所得クエリで用いる点 $(i,j)$ を追加する。
クエリ先読み後(pre_set後)、セグ木を構築する。
$[l, r) \times [d, u)$ の長方形に $f$ を作用させる。
$(i, j)$ の値を所得する。
#pragma once #include <bit> #include <utility> #include <vector> #include "../data_structure/compress.hpp" #include "../data_structure/dual_segtree.hpp" namespace ebi { template <class F, F (*merge)(F, F), F (*id)()> struct offline_dual_segtree_2d { offline_dual_segtree_2d() = default; void pre_set(std::pair<int, int> p) { ps.emplace_back(p); } void build() { for (auto [x, y] : ps) { xs.add(x); } xs.build(); sz = std::bit_ceil((unsigned int)xs.size()); ys.resize(2 * sz); for (auto [x, y] : ps) { int i = xs.get(x) + sz; ys[i].add(y); while (i > 1) { i >>= 1; ys[i].add(y); } } for (auto i : std::views::iota(0, 2 * sz)) { ys[i].build(); seg.emplace_back(dual_segtree<F, merge, id>(ys[i].size())); } } F get(int i, int j) { i = xs.get(i) + sz; F x = seg[i].get(ys[i].get(j)); while (i > 1) { i >>= 1; x = merge(x, seg[i].get(ys[i].get(j))); } return x; } void apply(int l, int d, int r, int u, F f) { l = xs.get(l) + sz; r = xs.get(r) + sz; while (l < r) { if (l & 1) { seg[l].apply(ys[l].get(d), ys[l].get(u), f); l++; } if (r & 1) { r--; seg[r].apply(ys[r].get(d), ys[r].get(u), f); } l >>= 1; r >>= 1; } } private: int sz = 1; std::vector<std::pair<int, int>> ps; compress<int> xs; std::vector<compress<int>> ys; std::vector<dual_segtree<F, merge, id>> seg; }; } // namespace ebi
#line 2 "data_structure/offline_dual_segtree_2d.hpp" #include <bit> #include <utility> #include <vector> #line 2 "data_structure/compress.hpp" #include <algorithm> #include <cassert> #line 6 "data_structure/compress.hpp" namespace ebi { template <class T> struct compress { private: std::vector<T> cp; public: compress() = default; compress(std::vector<T> cp_) : cp(cp_) { build(); } void build() { std::sort(cp.begin(), cp.end()); cp.erase(std::unique(cp.begin(), cp.end()), cp.end()); } void add(const T &val) { cp.emplace_back(val); } int get(const T &val) const { return std::lower_bound(cp.begin(), cp.end(), val) - cp.begin(); } int size() const { return cp.size(); } bool find(const T &val) const { auto itr = std::lower_bound(cp.begin(), cp.end(), val); if (itr == cp.end()) return false; else return *itr == val; } T val(int idx) const { assert(0 <= idx && idx < (int)cp.size()); return cp[idx]; } }; } // namespace ebi #line 2 "data_structure/dual_segtree.hpp" #line 5 "data_structure/dual_segtree.hpp" #include <ranges> #line 7 "data_structure/dual_segtree.hpp" namespace ebi { template <class F, F (*merge)(F, F), F (*id)()> struct dual_segtree { private: void all_apply(int i, F f) { d[i] = merge(f, d[i]); } void push(int i) { assert(i < sz); all_apply(2 * i, d[i]); all_apply(2 * i + 1, d[i]); d[i] = id(); } public: dual_segtree(int n) : dual_segtree(std::vector<F>(n, id())) {} dual_segtree(const std::vector<F> &a) : n(a.size()), sz(std::bit_ceil(a.size())), lg2(std::countr_zero((unsigned int)(sz))) { d = std::vector<F>(2 * sz, id()); for (int i : std::views::iota(sz, sz + n)) { d[i] = a[i - sz]; } } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= n); if (l == r) return; l += sz; r += sz; for (int i : std::views::iota(1, lg2 + 1) | std::views::reverse) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } } F get(int p) { assert(0 <= p && p < n); p += sz; for (int i : std::views::iota(1, lg2 + 1) | std::views::reverse) { push(p >> i); } return d[p]; } private: int n, sz, lg2; std::vector<F> d; }; } // namespace ebi #line 9 "data_structure/offline_dual_segtree_2d.hpp" namespace ebi { template <class F, F (*merge)(F, F), F (*id)()> struct offline_dual_segtree_2d { offline_dual_segtree_2d() = default; void pre_set(std::pair<int, int> p) { ps.emplace_back(p); } void build() { for (auto [x, y] : ps) { xs.add(x); } xs.build(); sz = std::bit_ceil((unsigned int)xs.size()); ys.resize(2 * sz); for (auto [x, y] : ps) { int i = xs.get(x) + sz; ys[i].add(y); while (i > 1) { i >>= 1; ys[i].add(y); } } for (auto i : std::views::iota(0, 2 * sz)) { ys[i].build(); seg.emplace_back(dual_segtree<F, merge, id>(ys[i].size())); } } F get(int i, int j) { i = xs.get(i) + sz; F x = seg[i].get(ys[i].get(j)); while (i > 1) { i >>= 1; x = merge(x, seg[i].get(ys[i].get(j))); } return x; } void apply(int l, int d, int r, int u, F f) { l = xs.get(l) + sz; r = xs.get(r) + sz; while (l < r) { if (l & 1) { seg[l].apply(ys[l].get(d), ys[l].get(u), f); l++; } if (r & 1) { r--; seg[r].apply(ys[r].get(d), ys[r].get(u), f); } l >>= 1; r >>= 1; } } private: int sz = 1; std::vector<std::pair<int, int>> ps; compress<int> xs; std::vector<compress<int>> ys; std::vector<dual_segtree<F, merge, id>> seg; }; } // namespace ebi