Hotman's Library

https://hotman78.github.io/cpplib/

競技プログラミングのC++のライブラリです

CC0ライセンスなので好きにコピーして下さい

themeはei1333/minimaをforkして使わせて頂いてます

Library Files

BBST/AVL

• BBST/AVL/base.hpp
• BBST/AVL/set.hpp

BBST/RBST

• BBST/RBST/base.hpp

BBST/splay_tree

• BBST/splay_tree/splay_tree_array.hpp
• BBST/splay_tree/splay_tree_array_ushi.hpp
• BBST/splay_tree/splay_tree_base.hpp
• BBST/splay_tree/splay_tree_map_ushi.hpp
• BBST/splay_tree/splay_tree_set.hpp

DP

• DP/monotone_minima.hpp

alga

• Maybe (alga/maybe.hpp)
• alga/monoid.hpp

data_structure

• data_structure/HLD_lazy.hpp
• data_structure/HLD_seg.hpp
• RMQ<O(N),O(1)> (data_structure/RMQ.hpp)
• RangeArgminQuery <O(N),O(1)> (data_structure/arg_rmq.hpp)
• BinaryHeap (data_structure/binary_heap.hpp)
• BinaryIndexedTree (data_structure/binary_indexed_tree.hpp)
• BinaryTrie (data_structure/binary_trie.hpp)
• BitVector (data_structure/bit_vector.hpp)
• cartesian_tree (data_structure/cartesian_tree.hpp)
• data_structure/cht.hpp
• 累積和(WIP) (data_structure/cumulative_sum.hpp)
• DisjointSparseTable (data_structure/disjoint_sparse_table.hpp)
• data_structure/euler_tour_tree.hpp
• FastSet(遅い) (data_structure/fast_set.hpp)
• HashMap (data_structure/hash_map.hpp)
• Kd木(WIP) (data_structure/kd_tree.hpp)
• マージ可能ヒープ(LeftistHeap) (data_structure/leftist_heap.hpp)
• LiChaoTree (data_structure/li_chao_tree.hpp)
• data_structure/link_cut_tree.hpp
• data_structure/my_deque.hpp
• マージ可能ヒープ(SkewHeap) (data_structure/skew_heap.hpp)
• data_structure/slide_max.hpp
• data_structure/slide_min.hpp
• data_structure/small_rmq.hpp
• SparseTable (data_structure/sparse_table.hpp)
• 平方分割(WIP) (data_structure/sqrtd.hpp)
• SWAG(Queue) (data_structure/swag.hpp)
• Trie(WIP) (data_structure/trie.hpp)
• WaveletMatrix(WIP) (data_structure/wavelet_matrix.hpp)
• data_structure/x_fast_trie.hpp

dsu

• dsu/UF_data.hpp
• dsu/UF_list.hpp
• 根とのPathの中での最小値を返すUnionFind (dsu/uf_min.hpp)
• Union Find (dsu/union_find.hpp)

functional

• 最大値 (functional/MAX.hpp)
• 最小値 (functional/MIN.hpp)
• 最大値とその位置 (functional/argmax.hpp)
• 最小値とその位置 (functional/argmin.hpp)
• 一次関数の合成 (functional/composite.hpp)
• 区間加算 (functional/range_add_and_range_sum.hpp)
• 更新 (functional/update.hpp)

give_us_tmp

• 重心分解 (give_us_tmp/centroid_decomposition.cpp)
• 素因数分解(高速) (give_us_tmp/factorize.cpp)
• 多項式乗算 (give_us_tmp/fft.cpp)
• 形式的冪級数 (give_us_tmp/fps.cpp)
• 素数判定(高速) (give_us_tmp/is_prime.cpp)
• give_us_tmp/lca.cpp
• give_us_tmp/mod_int.cpp

graph_tree

• ベルマンフォード法(WIP) (graph_tree/bellmanFord.hpp)
• 重心分解 (graph_tree/centroid_decomposition.hpp)
• 部分木の大きさ (graph_tree/child_size.hpp)
• 根からの深さ (graph_tree/depth.hpp)
• ダイクストラ法 O((E+V)logE) (graph_tree/dijkstra.hpp)
• ダイクストラ O(E+VlogE) (graph_tree/dijkstra_fast.hpp)
• 最大流(Dinic法) (graph_tree/dinic.hpp)
• graph_tree/distance.hpp
• 支配木 (graph_tree/dominator_tree.hpp)
• graph_tree/euler_tour.hpp
• グラフテンプレート (graph_tree/graph_template.hpp)
• LCA <O(N),O(1)>(HL分解と同等の速さ) (graph_tree/lca.hpp)
• LCA(HL分解)<O(N),O(logN)> (graph_tree/lca_short.hpp)
• graph_tree/lex_bfs.hpp
• 最大独立集合(V<=50) (graph_tree/maximum_independent_set.hpp)
• 最小費用流(CostScaling) (graph_tree/min_cost_flow.hpp)
• うしさんからパクってきた最小費用流 (graph_tree/min_cost_flow_ei.hpp)
• 最大流(push_relabel法O(V^2√E)) (graph_tree/push_relabel.hpp)
• 全方位木DP (graph_tree/reroot.hpp)
• 強連結成分分解 (graph_tree/scc.hpp)
• 最短経路木 O((E+V)logE) (graph_tree/shortest_path_tree_dijkstra.hpp)
• TopTree(WIP) (graph_tree/top_tree.hpp)
• トポロジカルソート (graph_tree/topological_sort.hpp)
• 木上の畳み込み(WIP) (graph_tree/tree_fold.hpp)
• 二辺連結成分分解 (graph_tree/two_edge_connectivity.hpp)
• 2-SAT (graph_tree/two_sat.hpp)

math

• 形式的冪級数(BASE) (math/FPS_base.hpp)
• 形式的冪級数(Integer) (math/FPS_long.hpp)
• 形式的冪級数(ModInt) (math/FPS_mint.hpp)
• math/NTT2d.hpp
• math/and_convolution.hpp
• 二分探索 (math/binary_search.hpp)
• 二分探索(double) (math/binary_search_double.hpp)
• カーマイケル関数 (math/carmichael_function.hpp)
• カタラン台形 (math/catalans_trapezoids.hpp)
• math/ceil_pow2.hpp
• 二項係数 mod P (math/comb.hpp)
• math/concave_max_plus_convolution.hpp
• 約数列挙 (math/divisor_list.hpp)
• オイラーのファイ関数 (math/euler_phi.hpp)
• math/fact_list.hpp
• \sum_{i=0}^{n-1}\floor(a*i+b/c) (math/floor_sum.hpp)
• ガーナーのアルゴリズム (math/garner.hpp)
• math/get_monomials.hpp
• 素数判定(高速) (math/is_prime.hpp)
• math/kth_root.hpp
• ラグランジュ補完(連続点->一点) (math/lagrange_interpolation.hpp)
• ModInt (math/mod_int.hpp)
• ModInt(1'000'000'007) (math/mod_int1000000007.hpp)
• ModInt(998'244'353) (math/mod_int998244353.hpp)
• ModInt (math/mod_int_dynamic.hpp)
• math/mod_inv.hpp
• 離散対数(ModLog) (math/mod_log.hpp)
• (x^y)%mod (math/mod_pow.hpp)
• ModSqrt (math/mod_sqrt.hpp)
• math/or_convolution.hpp
• osa_k法 (math/osa_k.hpp)
• math/partition_function.hpp
• 素因数分解(高速) (math/prime_factor.hpp)
• 素数列挙 (math/prime_list.hpp)
• math/stern_brocot_tree.cpp
• math/sum_power_poly.hpp
• math/sum_power_poly_limit.hpp
• テトレーション (math/tetration.hpp)
• トーシェント関数の和 (math/totient_sum.hpp)
• math/xor_convolution.hpp

math/test

• math/test/LC_sum_power_poly_limit.cpp

segment_tree

• 双対セグメント木 (segment_tree/dual_segment_tree.hpp)
• segment_tree/lazy_segment_tree.hpp
• セグメント木 (segment_tree/segment_tree.hpp)

string

• Aho-Corasick法 (string/AhoCorasick.hpp)
• Zアルゴリズム (string/Z_algorizm.hpp)
• Manacher (string/manacher.hpp)
• オンラインZアルゴリズム (string/online_Zalgo.hpp)
• ローリングハッシュ (string/rolling_hash.hpp)
• 部分列DP(WIP) (string/subseceqence.cpp)
• SuffixArray (string/suffix_array.hpp)
• SuffixAutomaton (string/suffix_automaton.hpp)
• Trie木 (string/trie.hpp)

util

• util/ACL.hpp
• util/cpp_int.hpp
• 高速入出力(WIP) (util/fastIO.hpp)
• util/int128.hpp
• util/make_case.hpp
• util/pbds.hpp
• util/random_gen.hpp
• util/template.hpp

Verification Files

data_structure/test

• data_structure/test/LC_RMQ.test.cpp
• data_structure/test/LC_binary_indexed_tree.test.cpp
• data_structure/test/LC_binary_trie.test.cpp
• data_structure/test/LC_birary_heap.test.cpp
• data_structure/test/LC_cartesian_tree.test.cpp
• data_structure/test/LC_disjoint_sparse_table.test.cpp
• data_structure/test/LC_fast_set.test.cpp
• data_structure/test/LC_hash_map.test.cpp
• data_structure/test/LC_line_add_get_min.test.cpp
• data_structure/test/LC_segment_add_get_min.test.cpp
• data_structure/test/LC_sparse_table.test.cpp
• data_structure/test/LC_swag.test.cpp
• data_structure/test/LC_wavelet_matrix.test.cpp

dsu/test

• dsu/test/union_find.test.cpp

graph_tree/test

• graph_tree/test/LC_centroid_decomposition.test.cpp
• graph_tree/test/LC_dijkstra.test.cpp
• graph_tree/test/LC_dijkstra_fast.test.cpp
• graph_tree/test/LC_dinic.test.cpp
• graph_tree/test/LC_dominator_tree.test.cpp
• graph_tree/test/LC_lca.test.cpp
• graph_tree/test/LC_lca_short.test.cpp
• graph_tree/test/LC_maximum_independent_set.test.cpp
• graph_tree/test/LC_min_cost_flow.test.cpp
• graph_tree/test/LC_push_relabel.test.cpp

math/test

• math/test/AOJ_binary_search.test.cpp
• math/test/AOJ_is_prime.test.cpp
• math/test/AOJ_prime_factor.test.cpp
• math/test/AOJ_prime_list.test.cpp
• math/test/LC_convolution_1000000007.test.cpp
• math/test/LC_convolution_998244353.test.cpp
• math/test/LC_floor_sum.test.cpp
• math/test/LC_interpolation.test.cpp
• math/test/LC_mod_log.test.cpp
• math/test/LC_mod_sqrt.test.cpp
• math/test/LC_prime_factor.test.cpp
• math/test/LC_tetration.test.cpp
• math/test/LC_totient_sum.test.cpp

segment_tree/test

• segment_tree/test/AOJ_dual_segment_tree.test.cpp
• segment_tree/test/AOJ_lazy_segment_tree.test.cpp
• segment_tree/test/LC_segment_tree.test.cpp

string/test

• string/test/LC_Z_algorizm.test.cpp
• string/test/LC_online_Z_algorizm.test.cpp
• string/test/YUKI_Aho_Corasick.test.cpp

util/test

• util/test/LC_Number_of_Substrings.test.cpp
• util/test/LC_Suffix_Array.test.cpp