algo

Library Files

lib/algorithm/

• めぐる式二分探索 (lib/algorithm/binary_search.hpp)
• 座標圧縮 (lib/algorithm/compress.hpp)
• 二次元累積和 (lib/algorithm/cumulative_sum.hpp)
• ダブリング (lib/algorithm/doubling.hpp)
• 半開区間 (lib/algorithm/interval.hpp)
• 転倒数 (lib/algorithm/inversion_number.hpp)
• 最長増加部分列 (lib/algorithm/lis.hpp)
• Mex (lib/algorithm/mex.hpp)
• Mo's algorithm (lib/algorithm/mo.hpp)
• lib/algorithm/offline_binomial_sum.hpp
• 回文判定 (lib/algorithm/palindrome.hpp)
• 累積和 (lib/algorithm/prefix_sum.hpp)
• ランレングス圧縮 (lib/algorithm/rle.hpp)
• Mo's algorithm (rollback) (lib/algorithm/rollback_mo.hpp)

lib/binary_tree/

• AVL木 (lib/binary_tree/avl_tree.hpp)
• 2分トライ木 (lib/binary_tree/binary_trie.hpp)
• フェニック木 (lib/binary_tree/fenwick_tree.hpp)
• フェニック木（区間加算、区間総和） (lib/binary_tree/fenwick_tree_raq.hpp)
• lib/binary_tree/ordered_set.hpp
• 2分パトリシア木 (lib/binary_tree/patricia_binary_trie.hpp)
• 区間をsetで管理するテク (lib/binary_tree/range_set.hpp)
• 領域木 (lib/binary_tree/range_tree.hpp)
• スケープゴート木 (lib/binary_tree/scapegoat_tree.hpp)
• lib/binary_tree/splay_tree.hpp
• Treap (lib/binary_tree/treap.hpp)
• 64分木 (lib/binary_tree/tree64.hpp)

lib/data_structure/

• 多倍長整数 (lib/data_structure/bigint.hpp)
• ウェーブレット行列 (lib/data_structure/compressed_wavelet_matrix.hpp)
• Disjoint Sparse Table (lib/data_structure/disjoint_sparse_table.hpp)
• 動的配列 (lib/data_structure/dynamic_sequence.hpp)
• 動的ウェーブレット行列 (lib/data_structure/dynamic_wavelet_matrix.hpp)
• 削除可能優先度付きキュー (lib/data_structure/erasable_priority_queue.hpp)
• flip set (lib/data_structure/flip_set.hpp)
• Li Chao Tree (lib/data_structure/li_chao_tree.hpp)
• 線形 Sparse Table (lib/data_structure/linear_sparse_table.hpp)
• merge-sort tree (lib/data_structure/merge_sort_tree.hpp)
• オフライン動的連結性 (lib/data_structure/offline_dynamic_connectivity.hpp)
• lib/data_structure/priority_k_sum.hpp
• スキップリスト (lib/data_structure/skip_list.hpp)
• スパーステーブル (lib/data_structure/sparse_table.hpp)
• Sliding Window Aggregation (lib/data_structure/swag.hpp)
• Undo可能両端キュー (lib/data_structure/undo_deque.hpp)
• ウェーブレット行列 (lib/data_structure/wavelet_matrix.hpp)
• 重み付きウェーブレット行列 (lib/data_structure/wavelet_matrix_rectangle_sum.hpp)

lib/fft/

• lib/fft/fft.hpp
• lib/fft/fft_mod.hpp
• lib/fft/formal_power_series.hpp
• lib/fft/garner.hpp
• min-plus convolution (lib/fft/monotone_minima.hpp)
• 畳み込み (lib/fft/ntt.hpp)
• 任意mod畳み込み (lib/fft/ntt_mod.hpp)
• lib/fft/subset_convolution.hpp

lib/flow/

• Hopcroft-Karp algorithm (lib/flow/hopcroft_karp.hpp)
• 最大流 (lib/flow/max_flow.hpp)
• 最小費用流 (lib/flow/min_cost_flow.hpp)

lib/geometry/

• Convex Hull Trick (lib/geometry/cht.hpp)
• 点 (lib/geometry/convex_hull.hpp)
• lib/geometry/geometry.hpp
• lib/geometry/geometry3d.hpp
• kd-tree (lib/geometry/kdtree.hpp)

lib/graph/

• ベルマンフォード法 (lib/graph/bellman_ford.hpp)
• 彩色数 (lib/graph/chromatic_number.hpp)
• 閉路検出 (lib/graph/cycle.hpp)
• ダイクストラ法 (lib/graph/dijkstra.hpp)
• ダイクストラ法 (lib/graph/dijkstra_potential.hpp)
• ワーシャルフロイド法 (lib/graph/floyd_warshall.hpp)
• functional graph (lib/graph/functional_graph.hpp)
• 重み付きグラフ (lib/graph/graph.hpp)
• lib/graph/grid.hpp
• クラスカル法 (lib/graph/kruskal.hpp)
• LowLink (lib/graph/lowlink.hpp)
• 隣接行列 (lib/graph/matrix_graph.hpp)
• 最大独立集合 (lib/graph/maximum_independent_set.hpp)
• なもりグラフ上のサイクル検出 (lib/graph/namori_graph.hpp)
• プリム法 (lib/graph/prim.hpp)
• 強連結成分分解 (lib/graph/scc.hpp)
• 全域木 (lib/graph/spanning_tree.hpp)
• SPFA (lib/graph/spfa.hpp)
• トポロジカルソート (lib/graph/topological_sort.hpp)
• 2-SAT (lib/graph/two_sat.hpp)

lib/heap/

• 二分ヒープ (lib/heap/binary_heap.hpp)
• フィボナッチヒープ (lib/heap/fibonacci_heap.hpp)
• interval heap (lib/heap/interval_heap.hpp)
• leftist heap (lib/heap/leftist_heap.hpp)
• 基数ヒープ (lib/heap/radix_heap.hpp)
• skew heap (lib/heap/skew_heap.hpp)

lib/internal/

• 動的完備辞書 (lib/internal/dynamic_bit_vector.hpp)
• 完備辞書 (lib/internal/internal_bit_vector.hpp)
• lib/internal/internal_csr.hpp
• lib/internal/internal_fft.hpp
• Montgomery modular multiplication (lib/internal/internal_math.hpp)
• lib/internal/internal_type_traits.hpp

lib/math/

• lib/math/bell.hpp
• Bostan-Mori法 (lib/math/bostan_mori.hpp)
• 拡張ユークリッドの互除法 (lib/math/chinese_rem.hpp)
• 二項係数 (lib/math/combination.hpp)
• lib/math/enumeration.hpp
• エラトステネスの篩 (lib/math/eratosthenes.hpp)
• 素因数分解 (lib/math/factorize.hpp)
• floor sum (lib/math/floor_sum.hpp)
• 分数ライブラリ (lib/math/fraction.hpp)
• lib/math/hashint.hpp
• きたまさ法 (lib/math/kitamasa.hpp)
• 線形篩 (lib/math/linear_sieve.hpp)
• lib/math/math.hpp
• 行列ライブラリ (lib/math/matrix.hpp)
• min of mod of linear (lib/math/min_linear.hpp)
• lib/math/modint.hpp
• n以下の素数を数える (lib/math/prime_counting.hpp)
• 素数ライブラリ (lib/math/prime_number.hpp)
• slope trick (lib/math/slope_trick.hpp)
• lib/math/sqrt.hpp

lib/persistent_ds/

• 部分永続Union-Find (lib/persistent_ds/partially_persistent_union_find.hpp)
• 永続配列 (lib/persistent_ds/persistent_array.hpp)
• 永続双対セグメント木 (lib/persistent_ds/persistent_dual_segment_tree.hpp)
• 永続遅延評価セグメント木 (lib/persistent_ds/persistent_lazy_segment_tree.hpp)
• 永続キュー (lib/persistent_ds/persistent_queue.hpp)
• 永続セグメント木 (lib/persistent_ds/persistent_segment_tree.hpp)
• 永続スタック (lib/persistent_ds/persistent_stack.hpp)
• 永続Union-Find (lib/persistent_ds/persistent_union_find.hpp)

lib/random/

• 疑似乱数生成器 SplitMix64 (lib/random/split_mix_64.hpp)
• 疑似乱数生成器 xoroshiro128++ (lib/random/xoroshiro128.hpp)
• 擬似乱数生成器 Xorshift (lib/random/xorshift.hpp)
• 疑似乱数生成器 xoshiro128++ (lib/random/xoshiro128.hpp)

lib/segtree/

• 双対セグメント木 (lib/segtree/dual_segment_tree.hpp)
• 動的遅延評価セグメント木 (lib/segtree/dynamic_lazy_segment_tree.hpp)
• 動的セグメント木 (lib/segtree/dynamic_segment_tree.hpp)
• 要素を特定のキー（条件）でフィルタリングして区間取得を行えるセグメント木 (lib/segtree/filtered_segment_tree.hpp)
• 遅延評価セグメント木 (lib/segtree/lazy_segment_tree.hpp)
• lib/segtree/monoid.hpp
• セグメント木 (lib/segtree/segment_tree.hpp)
• 二次元セグメント木 (lib/segtree/segment_tree_2d.hpp)
• lib/segtree/segment_tree_raq.hpp

lib/string/

• Aho Corasick法 (lib/string/aho_corasick.hpp)
• lib/string/converter.hpp
• KMP法 (lib/string/kmp.hpp)
• 最長共通接頭辞 (lib/string/lcp.hpp)
• Manacher (lib/string/manacher.hpp)
• lib/string/parenthesis.hpp
• ローリングハッシュ (lib/string/rolling_hash.hpp)
• Suffix Array (lib/string/suffix_array.hpp)
• lib/string/suffix_automaton.hpp
• lib/string/suffix_tree.hpp
• Trie (lib/string/trie.hpp)
• Z algorithm (lib/string/z_algorithm.hpp)

lib/template/

• lib/template/atcoder.hpp
• lib/template/library_checker.hpp
• lib/template/macro.hpp
• lib/template/sonic.hpp
• lib/template/template.hpp
• lib/template/vector.hpp

lib/tree/

• lib/tree/auxiliary_tree.hpp
• Cartesian Tree (lib/tree/cartesian_tree.hpp)
• 重心分解 (lib/tree/centroid_decomposition.hpp)
• DSU on Tree (lib/tree/dsu_on_tree.hpp)
• 動的Union-Find (lib/tree/dynamic_union_find.hpp)
• オイラーツアー (lib/tree/euler_tour.hpp)
• lib/tree/euler_tour_tree.hpp
• HL分解 (lib/tree/hld.hpp)
• lib/tree/linear_lca.hpp
• Link-Cut Tree (lib/tree/link_cut_tree.hpp)
• 回文木 (lib/tree/palindromic_tree.hpp)
• 全方位木dp (lib/tree/rerooting.hpp)
• Segment Tree on Tree (lib/tree/segment_tree_on_tree.hpp)
• Static Top Tree (lib/tree/static_top_tree.hpp)
• Stern-Brocot 木 (lib/tree/stern_brocot_tree.hpp)
• 木の距離を求める (lib/tree/tree_function.hpp)
• Undo可能Union-Find (lib/tree/undo_union_find.hpp)
• 素集合データ構造 (lib/tree/union_find.hpp)
• 重み付き素集合データ構造 (lib/tree/weighted_union_find.hpp)

Verification Files

test/aoj/alds1/

• test/aoj/alds1/interval_heap.test.cpp
• test/aoj/alds1/inversion_number.test.cpp
• test/aoj/alds1/kitamasa.test.cpp
• test/aoj/alds1/kmp.test.cpp
• test/aoj/alds1/leftist_heap.test.cpp
• test/aoj/alds1/prime_numbers.test.cpp
• test/aoj/alds1/prime_numbers2.test.cpp
• test/aoj/alds1/rolling_hash.test.cpp
• test/aoj/alds1/skew_heap.test.cpp
• test/aoj/alds1/suffix_array.test.cpp

test/aoj/cgl/

• test/aoj/cgl/convex_hull.test.cpp
• test/aoj/cgl/counter-clockwise.test.cpp
• test/aoj/cgl/cross_point.test.cpp
• test/aoj/cgl/intersection.test.cpp
• test/aoj/cgl/parallel_orthogonal.test.cpp
• test/aoj/cgl/projection.test.cpp
• test/aoj/cgl/reflection.test.cpp

test/aoj/challenge/

• test/aoj/challenge/0009.test.cpp
• test/aoj/challenge/1208.test.cpp
• test/aoj/challenge/1276.1.test.cpp
• test/aoj/challenge/1276.test.cpp
• test/aoj/challenge/1508.test.cpp
• test/aoj/challenge/2207.test.cpp
• test/aoj/challenge/2208.test.cpp
• test/aoj/challenge/2235.test.cpp
• test/aoj/challenge/2270.test.cpp
• test/aoj/challenge/2426.1.test.cpp
• test/aoj/challenge/2426.test.cpp
• test/aoj/challenge/2559.2.test.cpp
• test/aoj/challenge/2559.test.cpp
• test/aoj/challenge/2763.test.cpp
• test/aoj/challenge/2834.test.cpp
• test/aoj/challenge/2871.test.cpp
• test/aoj/challenge/2880.test.cpp
• test/aoj/challenge/2891.test.cpp
• test/aoj/challenge/2934.test.cpp
• test/aoj/challenge/3163.test.cpp

test/aoj/course/

• test/aoj/course/ALDS1_14_D.test.cpp
• test/aoj/course/ITP2_1_B.test.cpp

test/aoj/dpl/

• test/aoj/dpl/bell.test.cpp
• test/aoj/dpl/longest_increasing_subsequence.test.cpp
• test/aoj/dpl/stirling.test.cpp

test/aoj/dsl/

• test/aoj/dsl/dynamic_rmq.test.cpp
• test/aoj/dsl/range_search.test.cpp
• test/aoj/dsl/raq_rmq.test.cpp
• test/aoj/dsl/raq_rsq.test.cpp
• test/aoj/dsl/rmq.2.test.cpp
• test/aoj/dsl/rmq.test.cpp
• test/aoj/dsl/rmq_ruq.test.cpp
• test/aoj/dsl/rsq.test.cpp
• test/aoj/dsl/rsq_ruq.test.cpp
• test/aoj/dsl/ruq.test.cpp
• test/aoj/dsl/union_find.test.cpp
• test/aoj/dsl/weighted_union_find.test.cpp

test/aoj/grl/

• test/aoj/grl/articulation_points.test.cpp
• test/aoj/grl/bellman_ford.test.cpp
• test/aoj/grl/bipartite_matching.2.test.cpp
• test/aoj/grl/bipartite_matching.test.cpp
• test/aoj/grl/bridges.test.cpp
• test/aoj/grl/cycle.test.cpp
• test/aoj/grl/dijkstra.test.cpp
• test/aoj/grl/floyd_warshall.test.cpp
• test/aoj/grl/hld.test.cpp
• test/aoj/grl/kruskal.test.cpp
• test/aoj/grl/max_flow.test.cpp
• test/aoj/grl/min_cost_flow.test.cpp
• test/aoj/grl/prim.test.cpp
• test/aoj/grl/range_query_on_tree.test.cpp
• test/aoj/grl/range_query_on_tree_2.test.cpp
• test/aoj/grl/scc.test.cpp
• test/aoj/grl/spfa.test.cpp
• test/aoj/grl/topological_sort.test.cpp

test/aoj/jag/

• test/aoj/jag/aho_corasick.test.cpp
• test/aoj/jag/doubling.test.cpp
• test/aoj/jag/dsu_on_tree.test.cpp
• test/aoj/jag/dynamic_union_find.test.cpp
• test/aoj/jag/functional_graph.test.cpp
• test/aoj/jag/hash_int.test.cpp
• test/aoj/jag/hopcroft_karp.2.test.cpp
• test/aoj/jag/hopcroft_karp.test.cpp
• test/aoj/jag/rolling_hash.2.test.cpp
• test/aoj/jag/rolling_hash.test.cpp

test/aoj/joi/

• test/aoj/joi/prefix_sum.test.cpp
• test/aoj/joi/priority_k_sum.test.cpp
• test/aoj/joi/rle.test.cpp
• test/aoj/joi/undo_union_find.test.cpp

test/aoj/ntl/

• test/aoj/ntl/addition.test.cpp
• test/aoj/ntl/difference.test.cpp
• test/aoj/ntl/division.test.cpp
• test/aoj/ntl/multiplication.test.cpp
• test/aoj/ntl/multiplication2.test.cpp
• test/aoj/ntl/power.test.cpp
• test/aoj/ntl/prime_factorize.test.cpp
• test/aoj/ntl/remainder.test.cpp

test/yosupo/convolution/

• test/yosupo/convolution/bitwise_and_convolution.test.cpp
• test/yosupo/convolution/bitwise_xor_convolution.test.cpp
• test/yosupo/convolution/convolution.test.cpp
• test/yosupo/convolution/convolution_mod.test.cpp
• test/yosupo/convolution/gcd_convolution.test.cpp
• test/yosupo/convolution/lcm_convolution.test.cpp
• test/yosupo/convolution/min_plus_convolution_convex_arbitrary.test.cpp
• test/yosupo/convolution/min_plus_convolution_convex_convex.cpp

test/yosupo/data_structure/

• test/yosupo/data_structure/addition_of_big_integers.test.cpp
• test/yosupo/data_structure/binary_trie.test.cpp
• test/yosupo/data_structure/dynamic_tree_vertex_add_path_sum.test.cpp
• test/yosupo/data_structure/line_add_get_min.test.cpp
• test/yosupo/data_structure/orderd_set.2.test.cpp
• test/yosupo/data_structure/orderd_set.3.test.cpp
• test/yosupo/data_structure/orderd_set.4.test.cpp
• test/yosupo/data_structure/orderd_set.5.test.cpp
• test/yosupo/data_structure/orderd_set.6.test.cpp
• test/yosupo/data_structure/orderd_set.test.cpp
• test/yosupo/data_structure/patricia_binary_trie.test.cpp
• test/yosupo/data_structure/persistent_queue.test.cpp
• test/yosupo/data_structure/persistent_range_affine_range_sum.test.cpp
• test/yosupo/data_structure/persistent_union_find.test.cpp
• test/yosupo/data_structure/point_add_range_sum.test.cpp
• test/yosupo/data_structure/point_add_rectangle_sum.2.test.cpp
• test/yosupo/data_structure/point_add_rectangle_sum.test.cpp
• test/yosupo/data_structure/point_set_range_composite.test.cpp
• test/yosupo/data_structure/point_set_range_composite_large_array.test.cpp
• test/yosupo/data_structure/point_set_range_frequency.test.cpp
• test/yosupo/data_structure/predecessor_problem.test.cpp
• test/yosupo/data_structure/queue_operate_all_composite.test.cpp
• test/yosupo/data_structure/range_affine_range_sum.test.cpp
• test/yosupo/data_structure/range_affine_range_sum_large_array.test.cpp
• test/yosupo/data_structure/range_kth_smallest.2.test.cpp
• test/yosupo/data_structure/range_kth_smallest.test.cpp
• test/yosupo/data_structure/rectangle_sum.test.cpp
• test/yosupo/data_structure/segment_add_get_min.test.cpp
• test/yosupo/data_structure/static_range_frequency.2.test.cpp
• test/yosupo/data_structure/static_range_frequency.test.cpp
• test/yosupo/data_structure/static_range_inversions.test.cpp
• test/yosupo/data_structure/static_range_sum.test.cpp
• test/yosupo/data_structure/static_rmq.2.test.cpp
• test/yosupo/data_structure/static_rmq.3.test.cpp
• test/yosupo/data_structure/static_rmq.test.cpp
• test/yosupo/data_structure/undo_union_find.test.cpp
• test/yosupo/data_structure/unionfind.test.cpp
• test/yosupo/data_structure/unionfind_with_potential.test.cpp

test/yosupo/enumerative_conbinatorics/

• test/yosupo/enumerative_conbinatorics/bell_number.test.cpp

test/yosupo/geometry/

• test/yosupo/geometry/sort_points_by_argument.test.cpp

test/yosupo/graph/

• test/yosupo/graph/chromatic_number.test.cpp
• test/yosupo/graph/matching_on_bipartite_garph.2.test.cpp
• test/yosupo/graph/matching_on_bipartite_garph.test.cpp
• test/yosupo/graph/maximum_independent_set.test.cpp
• test/yosupo/graph/shortest_path.test.cpp
• test/yosupo/graph/strongly_connected_components.test.cpp

test/yosupo/math/

• test/yosupo/math/bostan_mori.test.cpp
• test/yosupo/math/floor_sum.test.cpp
• test/yosupo/math/kth_root_integer.test.cpp
• test/yosupo/math/min_linear.test.cpp
• test/yosupo/math/montmort_number.test.cpp
• test/yosupo/math/number_of_subsequences.test.cpp
• test/yosupo/math/sqrt_mod.test.cpp

test/yosupo/matrix/

• test/yosupo/matrix/determinant_of_matrix.test.cpp
• test/yosupo/matrix/matrix_product.test.cpp

test/yosupo/number_theory/

• test/yosupo/number_theory/counting_primes.test.cpp
• test/yosupo/number_theory/factorize.test.cpp

test/yosupo/other/

• test/yosupo/other/longest_increasing_subsequence.test.cpp
• test/yosupo/other/two_sat.test.cpp

test/yosupo/polynomial/

• test/yosupo/polynomial/division_of_polynomials.test.cpp
• test/yosupo/polynomial/exp_of_formal_power_series.test.cpp
• test/yosupo/polynomial/inv_of_formal_power_series.test.cpp
• test/yosupo/polynomial/log_of_formal_power_series.test.cpp
• test/yosupo/polynomial/multipoint_evaluation.test.cpp
• test/yosupo/polynomial/polynomial_interpolation.test.cpp
• test/yosupo/polynomial/polynomial_taylor_shift.test.cpp
• test/yosupo/polynomial/pow_of_formal_power_series.test.cpp
• test/yosupo/polynomial/product_of_polynomial_sequence.test.cpp

test/yosupo/sample/

• test/yosupo/sample/a+b.test.cpp
• test/yosupo/sample/many_a+b.test.cpp

test/yosupo/set_power_series/

• test/yosupo/set_power_series/subset_convolution.test.cpp

test/yosupo/string/

• test/yosupo/string/enumerate_palindromes.test.cpp
• test/yosupo/string/longest_common_substring.test.cpp
• test/yosupo/string/number_of_substring.2.test.cpp
• test/yosupo/string/number_of_substring.3.test.cpp
• test/yosupo/string/number_of_substring.4.test.cpp
• test/yosupo/string/number_of_substring.test.cpp
• test/yosupo/string/suffix_array.2.test.cpp
• test/yosupo/string/suffix_array.test.cpp
• test/yosupo/string/zalgorithm.2.test.cpp
• test/yosupo/string/zalgorithm.test.cpp

test/yosupo/tree/

• test/yosupo/tree/cartesian_tree.test.cpp
• test/yosupo/tree/jump_on_tree.test.cpp
• test/yosupo/tree/lowest_common_ancestor.2.test.cpp
• test/yosupo/tree/lowest_common_ancestor.test.cpp
• test/yosupo/tree/point_set_tree_path_composite_sum_fixed_root.test.cpp
• test/yosupo/tree/tree_diameter.test.cpp
• test/yosupo/tree/tree_path_composite_sum.test.cpp
• test/yosupo/tree/vertex_add_path_sum.test.cpp
• test/yosupo/tree/vertex_add_subtree_sum.2.test.cpp
• test/yosupo/tree/vertex_add_subtree_sum.test.cpp
• test/yosupo/tree/vertex_set_path_composite.test.cpp

test/yukicoder/

• test/yukicoder/0263.test.cpp
• test/yukicoder/0273.test.cpp
• test/yukicoder/0416.test.cpp
• test/yukicoder/0551.test.cpp
• test/yukicoder/0583.test.cpp
• test/yukicoder/0618.test.cpp
• test/yukicoder/0674.test.cpp
• test/yukicoder/0715.test.cpp
• test/yukicoder/0843.test.cpp
• test/yukicoder/0901.test.cpp
• test/yukicoder/1013.test.cpp
• test/yukicoder/1028.test.cpp
• test/yukicoder/1036.test.cpp
• test/yukicoder/1097.test.cpp
• test/yukicoder/1209.test.cpp
• test/yukicoder/1211.test.cpp
• test/yukicoder/1242.2.test.cpp
• test/yukicoder/1242.test.cpp
• test/yukicoder/1611.test.cpp
• test/yukicoder/1790.test.cpp
• test/yukicoder/1977.test.cpp
• test/yukicoder/2206.test.cpp
• test/yukicoder/3327.test.cpp