shogo-library

競技プログラミング用の C++ ライブラリです。 ソースコードは shogo314/shogo-library にあります。

src/ を include パスに追加して、必要なヘッダを include します。

#include "data_structures/segtree.hpp"
#include "math/modint.hpp"

データ構造には algebra/ のモノイドを渡します。ラムダ式から作ることもできます。

SegTree<monoid::Max<int>> seg(n);
SegTree seg2(v, Monoid([](int a, int b) { return a + b; }, 0));
LazySegTree<acted_monoid::AffineSum<mint>> lseg(v);

Library Files

src/algebra

• 作用素付きモノイドの定義 (src/algebra/acted-monoid.hpp)
• 群の定義 (src/algebra/group.hpp)
• モノイドの定義 (src/algebra/monoid.hpp)

src/base

• ビット演算 (src/base/bit.hpp)
• コンテナに対する関数 (sorted, max, sum など) (src/base/container_func.hpp)
• 汎用関数 (chmin, chmax, 二分探索など) (src/base/functions.hpp)
• 空白区切り出力、iostreamのオーバーロード (src/base/io.hpp)
• マクロ (rep など) (src/base/macro.hpp)
• Python の range のような整数列 (src/base/range.hpp)
• 出力をそのままコンストラクタに使える文字列化 (repr) (src/base/repr.hpp)
• 型特性 (src/base/traits.hpp)
• 型の別名 (src/base/type_alias.hpp)
• vector に対する演算子と関数 (src/base/vector_func.hpp)

src/data_structures

• Binary Trie (src/data_structures/binary-trie.hpp)
• 円環 (src/data_structures/circular-ring.hpp)
• Convex Hull Trick (src/data_structures/convex-hull-trick.hpp)
• 区間内の値の個数を数えるセグメント木 (src/data_structures/counter-segtree.hpp)
• 値の個数を数える多重集合 (Counter) (src/data_structures/counter.hpp)
• imos法で区間作用、1点取得 (src/data_structures/imos.hpp)
• 半開区間の集合 (src/data_structures/interval-set.hpp)
• 遅延伝搬セグメント木 (src/data_structures/lazy-segtree.hpp)
• マージソートツリー (src/data_structures/merge-sort-tree.hpp)
• 1点更新・全体の mex 取得 (src/data_structures/mex-update.hpp)
• 可換モノイドを乗せるUnionFind (src/data_structures/monoid-unionfind.hpp)
• ポテンシャル付きUnionFind (src/data_structures/potentialized-unionfind.hpp)
• 上位 K 個の値とその個数 (src/data_structures/priority_counter.hpp)
• 2次元セグメント木 (src/data_structures/segtree-2d.hpp)
• Segment Tree Beats (src/data_structures/segtree-beats.hpp)
• セグメント木 (src/data_structures/segtree.hpp)
• おたまじゃくし配列 (src/data_structures/tadpole-array.hpp)
• UnionFind (src/data_structures/unionfind.hpp)

src/geometry

• 幾何ベクトル (src/geometry/vector.hpp)

src/graph

• ファンクショナルグラフ (src/graph/functional-graph.hpp)
• グラフ (src/graph/graph.hpp)
• グラフに関する関数 (src/graph/graph_util.hpp)
• 全方位木DP (src/graph/rerooting-dp.hpp)
• 木の汎用テンプレート (src/graph/tree.hpp)

src/math

• 組み合わせ (src/math/combinatorics.hpp)
• 形式的冪級数 (src/math/fps.hpp)
• inf を持つ整数型 (src/math/infint.hpp)
• 行列 (src/math/matrix.hpp)
• 四則演算において自動で mod を取るクラス (src/math/modint.hpp)
• 数論 (逆元、中国剰余定理、畳み込みなど) (src/math/number-theory.hpp)
• 整数の平方根 (src/math/sqrt.hpp)

src/others

• Mo's algorithm (src/others/mo.hpp)

src/string

• ローリングハッシュ (src/string/rolling-hash.hpp)
• Z-algorithm (src/string/string.hpp)

Verification Files

test/aoj

• test/aoj/0022.test.cpp
• test/aoj/0029.test.cpp
• test/aoj/1160.test.cpp
• test/aoj/1595.test.cpp
• test/aoj/3314.test.cpp
• test/aoj/3372.test.cpp
• test/aoj/alds1-1-b.test.cpp
• test/aoj/alds1-11-d.1.test.cpp
• test/aoj/alds1-11-d.2.test.cpp
• test/aoj/alds1-14-b.test.cpp
• test/aoj/alds1-4-b.test.cpp
• test/aoj/alds1-4-d.test.cpp
• test/aoj/cgl-2-b.test.cpp
• test/aoj/cgl-2-c.test.cpp
• test/aoj/cgl-3-a.test.cpp
• test/aoj/cgl-3-b.test.cpp
• test/aoj/cgl-3-c.test.cpp
• test/aoj/cgl-4-a.test.cpp
• test/aoj/cgl-5-a.test.cpp
• test/aoj/dpl-5-b.1.test.cpp
• test/aoj/dpl-5-b.2.test.cpp
• test/aoj/dpl-5-d.1.test.cpp
• test/aoj/dpl-5-d.2.test.cpp
• test/aoj/dpl-5-e.lucas.test.cpp
• test/aoj/dpl-5-e.test.cpp
• test/aoj/dpl-5-f.test.cpp
• test/aoj/dsl-1-b.1.test.cpp
• test/aoj/dsl-1-b.2.test.cpp
• test/aoj/dsl-2-a.test.cpp
• test/aoj/dsl-2-b.test.cpp
• test/aoj/dsl-2-f.test.cpp
• test/aoj/dsl-2-g.test.cpp
• test/aoj/dsl-2-h.1.test.cpp
• test/aoj/dsl-2-h.2.test.cpp
• test/aoj/dsl-2-i.test.cpp
• test/aoj/dsl-4-a.test.cpp
• test/aoj/dsl-5-a.test.cpp
• test/aoj/grl-1-b.test.cpp
• test/aoj/grl-1-c.test.cpp
• test/aoj/grl-4-a.test.cpp
• test/aoj/grl-5-a.test.cpp
• test/aoj/grl-5-b.test.cpp
• test/aoj/itp1-1-a.binary-trie.test.cpp
• test/aoj/itp1-10-c.test.cpp
• test/aoj/itp1-2-c.test.cpp
• test/aoj/itp1-4-d.test.cpp
• test/aoj/itp1-6-a.test.cpp
• test/aoj/itp1-7-b.test.cpp
• test/aoj/itp2-10-c.test.cpp
• test/aoj/itp2-3-b.1.test.cpp
• test/aoj/itp2-3-b.2.test.cpp
• test/aoj/itp2-3-b.3.test.cpp
• test/aoj/itp2-3-c.test.cpp
• test/aoj/itp2-5-a.1.test.cpp
• test/aoj/itp2-5-a.2.test.cpp
• test/aoj/itp2-5-b.test.cpp
• test/aoj/itp2-7-d.test.cpp
• test/aoj/jag-summer-2971.test.cpp
• test/aoj/ntl-1-c.test.cpp
• test/aoj/ntl-1-e.test.cpp

test/unittest

• test/unittest/acted-monoid.test.cpp
• test/unittest/binary-trie.test.cpp
• test/unittest/bit.test.cpp
• test/unittest/circular-ring.test.cpp
• test/unittest/combinatorics.test.cpp
• test/unittest/container-func-member.test.cpp
• test/unittest/container-func.test.cpp
• test/unittest/counter-segtree.test.cpp
• test/unittest/counter.test.cpp
• test/unittest/fps.test.cpp
• test/unittest/functional-graph.2.test.cpp
• test/unittest/functional-graph.test.cpp
• test/unittest/functions.test.cpp
• test/unittest/graph-util.test.cpp
• test/unittest/graph.test.cpp
• test/unittest/imos.test.cpp
• test/unittest/infint.test.cpp
• test/unittest/interval-set.test.cpp
• test/unittest/io.test.cpp
• test/unittest/macro.test.cpp
• test/unittest/matrix.test.cpp
• test/unittest/mex-update.test.cpp
• test/unittest/mo.test.cpp
• test/unittest/modint.test.cpp
• test/unittest/monoid-unionfind.test.cpp
• test/unittest/monoid.test.cpp
• test/unittest/potentialized-unionfind.test.cpp
• test/unittest/priority_counter.test.cpp
• test/unittest/range.test.cpp
• test/unittest/repr.test.cpp
• test/unittest/rerooting-dp.test.cpp
• test/unittest/rolling-hash.test.cpp
• test/unittest/segtree-beats.test.cpp
• test/unittest/tadpole-array.test.cpp
• test/unittest/tree.test.cpp
• test/unittest/unionfind.test.cpp
• test/unittest/vector-func.test.cpp
• test/unittest/vector.test.cpp

test/yosupo

• test/yosupo/area-of-union-of-rectangles.1.test.cpp
• test/yosupo/area-of-union-of-rectangles.2.test.cpp
• test/yosupo/associative-array.test.cpp
• test/yosupo/binomial-coefficient-prime-mod.1.test.cpp
• test/yosupo/binomial-coefficient-prime-mod.2.test.cpp
• test/yosupo/binomial-coefficient.test.cpp
• test/yosupo/convolution-mod-1000000007.test.cpp
• test/yosupo/convolution-mod-2-64.test.cpp
• test/yosupo/convolution-mod.test.cpp
• test/yosupo/counting-spanning-tree-undirected.test.cpp
• test/yosupo/division-of-polynomials.test.cpp
• test/yosupo/enumerate-palindromes.test.cpp
• test/yosupo/enumerate-quotients.test.cpp
• test/yosupo/exp-of-fps.test.cpp
• test/yosupo/inv-of-fps.test.cpp
• test/yosupo/jump-on-tree.test.cpp
• test/yosupo/lca.1.test.cpp
• test/yosupo/lca.2.test.cpp
• test/yosupo/lca.3.test.cpp
• test/yosupo/lca.4.test.cpp
• test/yosupo/line-add-get-min.test.cpp
• test/yosupo/log-of-fps.test.cpp
• test/yosupo/matrix-det.test.cpp
• test/yosupo/minimum-spanning-tree.test.cpp
• test/yosupo/partition-function_1.test.cpp
• test/yosupo/partition-function_2.test.cpp
• test/yosupo/point-add-range-sum.1.test.cpp
• test/yosupo/point-add-range-sum.2.test.cpp
• test/yosupo/point-add-rectangle-sum.test.cpp
• test/yosupo/point-set-range-composite.1.test.cpp
• test/yosupo/point-set-range-composite.2.test.cpp
• test/yosupo/point-set-range-composite.3.test.cpp
• test/yosupo/point-set-range-composite.4.test.cpp
• test/yosupo/point-set-range-frequency.test.cpp
• test/yosupo/polynomial-taylor-shift.test.cpp
• test/yosupo/pow-of-fps.test.cpp
• test/yosupo/range-affine-point-get.test.cpp
• test/yosupo/range-affine-range-sum.1.test.cpp
• test/yosupo/range-affine-range-sum.2.test.cpp
• test/yosupo/range-affine-range-sum.3.test.cpp
• test/yosupo/range-chmin-chmax-add-range-sum.1.test.cpp
• test/yosupo/range-chmin-chmax-add-range-sum.2.test.cpp
• test/yosupo/range-set-range-composite.test.cpp
• test/yosupo/rectangle-sum.1.test.cpp
• test/yosupo/rectangle-sum.2.test.cpp
• test/yosupo/segment-add-get-min.test.cpp
• test/yosupo/set-xor-min.test.cpp
• test/yosupo/sharp-p-subset-sum.test.cpp
• test/yosupo/shortest-path.test.cpp
• test/yosupo/sort-points-by-argument.1.test.cpp
• test/yosupo/sort-points-by-argument.2.test.cpp
• test/yosupo/static-range-inversions-query.test.cpp
• test/yosupo/static-range-sum.test.cpp
• test/yosupo/tree-diameter.test.cpp
• test/yosupo/unionfind-with-potential-non-commutative-group.test.cpp
• test/yosupo/unionfind.test.cpp
• test/yosupo/vertex-add-subtree-sum.test.cpp
• test/yosupo/zalgorithm.test.cpp

test/yukicoder

• test/yukicoder/1036.1.test.cpp
• test/yukicoder/1036.2.test.cpp
• test/yukicoder/117.test.cpp
• test/yukicoder/1641.test.cpp
• test/yukicoder/186.test.cpp
• test/yukicoder/187.test.cpp
• test/yukicoder/2292.test.cpp
• test/yukicoder/3652.test.cpp
• test/yukicoder/674.1.test.cpp
• test/yukicoder/674.2.test.cpp
• test/yukicoder/898.test.cpp
• test/yukicoder/rotate-enlarge_1.test.cpp
• test/yukicoder/rotate-enlarge_2.test.cpp
• test/yukicoder/search-oji.test.cpp