competitive-programming-library

Library Files

data_structure

• Binary Indexed Tree (data_structure/binary_indexed_tree.hpp)
• Convex Hull Trick (非単調, online) (data_structure/convex_hull_trick.hpp)
• Dual Segment Tree / 双対セグメント木 (monoids, 完全二分木) (data_structure/dual_segment_tree.hpp)
• Dynamic Connectivity (offline, commutative monoids) (data_structure/dynamic_connectivity_offline.hpp)
• Euler Tour (subtree queries, with commutative monoids) (data_structure/euler_tour_subtree_query.hpp)
• Fully Indexable Dictionary / 完備辞書 (data_structure/fully_indexable_dictionary.hpp)
• Lazy Propagation Segment Tree / 遅延伝播セグメント木 (monoids, 赤黒木) (data_structure/lazy_propagation_red_black_tree.hpp)
• Lazy Propagation Segment Tree / 遅延伝播セグメント木 (monoids, 完全二分木) (data_structure/lazy_propagation_segment_tree.hpp)
• Li-Chao tree (data_structure/li_chao_tree.hpp)
• Link-Cut tree (monoids without commutativity, vertex set + path get) (data_structure/link_cut_tree.hpp)
• Dual Segment Tree / 双対セグメント木 (列挙クエリ, 完全二分木) (data_structure/reporting_segment_tree.hpp)
• Segment Tree / セグメント木 (monoids, 完全二分木) (data_structure/segment_tree.hpp)
• Segment Tree Beats (range {chmin, chmax, add, update} + range {min, max, sum}, 完全二分木) (data_structure/segment_tree_beats.hpp)
• Sliding Window Aggregation / 含まれる要素の総和が $O(1)$ で取れる queue (可換とは限らない monoid が乗る) (data_structure/sliding_window_aggregation.hpp)
• Sparse Table (idempotent monoid) (data_structure/sparse_table.hpp)
• Union-Find Tree (data_structure/union_find_tree.hpp)
• Union-Find Tree (foldable with commutative monoids, undoable) (data_structure/union_find_tree_foldable_undoable.hpp)
• a disjoint set structure with monoid (data_structure/union_find_tree_with_monoid.hpp)
• Wavelet Matrix (data_structure/wavelet_matrix.hpp)

graph

• Bellman-Ford algorithm (graph/bellman_ford.hpp)
• Cartesian tree ($O(n)$) (graph/cartesian_tree.hpp)
• get a central path of a catapillar graph (graph/catapillar_graph.hpp)
• graph/connected_components.hpp
• get the diameter of a tree / 木の直径 (graph/diameter_of_tree.hpp)
• Dijkstra ($O((E + V) \log V)$) (graph/dijkstra.hpp)
• maximum flow / 最大流 (Dinic) (graph/dinic.hpp)
• Eulerian cycle (無向, 復元) (graph/euler_graph.hpp)
• Euler Tour (preorder) (graph/euler_tour_preorder.hpp)
• graph/format.hpp
• Namori cycle / なもり閉路 (graph/functional_graph.hpp)
• graph/is_connected_graph.hpp
• graph/is_simple_graph.hpp
• minimum spanning tree / 最小全域木 (Kruskal's method) (graph/kruskal.hpp)
• lowest common ancestor / 最小共通祖先 (前処理 $O(N)$ + $O(1)$, $\pm 1$ RMQ and sparse table) (graph/lowest_common_ancestor.hpp)
• 全域木の個数を数える (行列木定理) (graph/matrix_tree_theorem.hpp)
• minimum cost flow / 最小費用流 (primal-dual) (graph/minimum-cost-flow.hpp)
• graph/quotient_graph.hpp
• Shortest Path Faster Algorithm (graph/shortest_path_faster_algorithm.hpp)
• strongly connected components decomposition, Kosaraju's algorithm / 強連結成分分解 (graph/strongly_connected_components.hpp)
• subtree info / それぞれの部分木の size とか height とかをまとめて求めておいてくれるやつ (graph/subtree.hpp)
• topological sort (graph/topological_sort.hpp)
• graph/transpose_graph.hpp
• 木分解 (木幅 $t \le 2$) (graph/tree_decomposition.hpp)
• 虚樹 / virtual trees (graph/virtual_trees.hpp)
• K shortest simple paths (Yen's algorithm + Dijkstra, $O(K V (E + V) \log V)$) (graph/yen_algorithm.hpp)

hack

• hack/fastio.hpp
• hack/fastio_printer.hpp
• hack/fastio_scanner.hpp
• hack/stack_pivot.hpp

modulus

• the Bell number (前処理 $O(NK)$ + $O(1)$) (modulus/bell_number.hpp)
• combination / 組合せ ${} _ n C _ r$ (前処理 $O(n)$ + $O(1)$) (modulus/choose.hpp)
• combination / 組合せ ${} _ n C _ r$ (愚直 $O(r)$) (modulus/choose_simple.hpp)
• modulus/factorial.hpp
• formal power series / 形式的羃級数環 $\mathbb{Z}/n\mathbb{Z}\lbrack\lbrack x\rbrack\rbrack$ (modulus/formal_power_series.hpp)
• Garner's algorithm (modulus/garner.hpp)
• quotient ring / 剰余環 $\mathbb{Z}/n\mathbb{Z}$ (modulus/mint.hpp)
• $\mathbb{Z}$ の乗除算を $\mathbb{Z}/n\mathbb{Z}$ の上でやるデータ構造 (modulus/mint_with_zero.hpp)
• modulus/modinv.hpp
• discrete log / 離散対数 (the baby-step giant-step, $O(\sqrt{m})$) (modulus/modlog.hpp)
• modulus/modpow.hpp
• find the sqrt $b$ of $a$ modulo $p$ (modulus/modsqrt.hpp)
• 重複組合せ ${} _ n H _ r = {} _ {n + r - 1} C _ r$ (前処理 $O(n)$ + $O(1)$) (modulus/multichoose.hpp)
• 重複組合せ ${} _ n H _ r = {} _ {n + r - 1} C _ r$ (愚直 $O(r)$) (modulus/multichoose_simple.hpp)
• Number Theoretic Transformation (NTT) for Proth primes (modulus/number_theoretic_transformation.hpp)
• multiprecation on $\mathbb{Z}/n\mathbb{Z}[x]$ (modulus/number_theoretic_transformation_with_garner.hpp)
• the partition number (前処理 $O(NK)$ + $O(1)$) (modulus/partition_number.hpp)
• permutation / 順列 ${} _ n P _ r$ (前処理 $O(n)$ + $O(1)$) (modulus/permute.hpp)
• the Stirling number of the second kind (for given $N$, compute $S(N, \ast)$ in $O(N \log N)$) (modulus/stirling_number_of_the_second_kind_convolution.hpp)
• the Stirling number of the second kind ($O(K \log N)$) (modulus/stirling_number_of_the_second_kind_direct.hpp)
• the Stirling number of the second kind (前処理 $O(NK)$ + $O(1)$) (modulus/stirling_number_of_the_second_kind_table.hpp)
• twelvefold way / 写像12相 (modulus/twelvefold_way.hpp)

monoids

• monoids/chmin_chmax_add.hpp
• monoids/chmin_chmax_add_min_max_action.hpp
• monoids/dual.hpp
• monoids/gcd.hpp
• monoids/left.hpp
• monoids/left_action.hpp
• monoids/linear_function.hpp
• monoids/linear_function_plus_count_action.hpp
• monoids/matrix_template.hpp
• monoids/max.hpp
• monoids/max_index.hpp
• monoids/min.hpp
• monoids/min_count.hpp
• monoids/min_index.hpp
• monoids/min_max.hpp
• monoids/plus.hpp
• monoids/plus_count.hpp
• monoids/plus_max_action.hpp
• monoids/plus_min_action.hpp
• monoids/plus_min_count_action.hpp
• monoids/product.hpp
• monoids/reversible.hpp
• monoids/trivial.hpp
• monoids/trivial_action.hpp

number

• FFT convolution (number/fast_fourier_transformation.hpp)
• number/gcd.hpp
• number/inversion_number.hpp
• Karatsuba method ($O(n^{\log_2 3})$) (number/karatsuba.hpp)
• Lagrange interpolation (number/lagrange_interpolation.hpp)
• number/matrix.hpp
• number/matrix_template.hpp
• miller-rabin primality test (number/miller-rabin.hpp)
• number/primes.hpp
• number/primes_extra.hpp

old

• Andrew's Monotone Chain (old/a.inc.cpp)
• old/aho-corasick.inc.cpp
• the Bernoulli number (old/bernoulli-number.inc.cpp)
• old/bipartite-graph.inc.cpp
• old/boyer-moore.inc.cpp
• compute the distances from root (old/breadth-first-search.inc.cpp)
• get centers of a tree / 木の中心 (old/centers.inc.cpp)
• get centroids of a graph / 重心分解 (old/centroid-decomposition.inc.cpp)
• compare substrings of a string with O(1) using suffix arrays (old/comparable-view.inc.cpp)
• old/convex-hull-trick-with-monotonicity.inc.cpp
• old/convex-hull.inc.cpp
• cumulative sum (old/cumulative-sum.inc.cpp)
• old/dice.inc.cpp
• old/digit-dp.inc.cpp
• old/dijkstra.inc.cpp
• old/distributed-code-jam.inc.cpp
• old/dlopen.inc.cpp
• old/dominator-tree.inc.cpp
• a double-ended priority queue (old/double-ended-priority-queue.inc.cpp)
• the doubling technique (old/doubling.inc.cpp)
• old/dynamic-segment-tree.inc.cpp
• euler tour (old/euler-tour.inc.cpp)
• extended gcd (old/extgcd.inc.cpp)
• old/factoradic.inc.cpp
• a program to make the table (old/factorial-embed.inc.cpp)
• (upward) fast zeta transformation (old/fast-mobius-transformation.inc.cpp)
• old/ford-fulkerson.inc.cpp
• old/graphviz.inc.cpp
• heavy light decomposition / 重軽分解 (old/heavy_light_decomposition.inc.cpp)
• old/iterate.inc.cpp
• old/knapsack-problem-branch-and-bound.inc.cpp
• Morris-Pratt algorithm (old/knuth-morris-pratt.inc.cpp)
• old/linear-weighted-sum.inc.cpp
• old/longest-increasing-subsequence.inc.cpp
• old/marathon.inc.cpp
• old/matrix.inc.cpp
• old/maximum-independent-set.inc.cpp
• a structure to make a midpoint for given two points (old/midpoint.inc.cpp)
• old/palindrome.inc.cpp
• old/periodic-function-power.inc.cpp
• persistent array / 永続配列 (old/persistent-array.inc.cpp)
• old/persistent-randomized-binary-search-tree.inc.cpp
• old/point-int.inc.cpp
• old/polya-enumeration.inc.cpp
• old/popen2.inc.cpp
• enumerate primes in [2, n) with O(n log log n) (old/primes-small.inc.cpp)
• old/range-union-find-tree.inc.cpp
• old/rational.inc.cpp
• old/red-black-tree.inc.cpp
• the extended Mo's algorithm (old/rollback-square-decomposition.inc.cpp)
• a rolling hash (old/rolling-hash.inc.cpp)
• old/segment-tree-2d.inc.cpp
• old/simplex.inc.cpp
• old/skew-heap.inc.cpp
• the sliding window minimum algorithm (old/sliding-window.inc.cpp)
• old/string-skip-list.inc.cpp
• old/subset.inc.cpp
• old/suffix-array.inc.cpp
• old/ternary-search.inc.cpp
• old/treap.inc.cpp
• fold a rooted tree / 木DP (old/tree-dp.inc.cpp)
• old/trie-tree.inc.cpp
• 2-edge-connected components decomposition / 2-辺連結成分分解 (old/two-edge-connected-components.inc.cpp)
• 2-node-connected components decomposition / 2-頂点連結成分分解 (old/two-node-connected-components.inc.cpp)
• Warshall-Floyd algorithm (old/warshall-floyd.inc.cpp)
• old/xorshift.inc.cpp

python

• python/binary_search.py
• python/chinese_remainder_theorem.py
• python/choose.py
• python/extgcd.py
• python/matrix-modinv.py
• python/miller_rabin.py
• python/rational-gcd.py

string

• Longest Common Prefix / 最長共通接頭辞 (接尾辞配列, 前処理 $O(N (\log N)^2)$ + $O(1)$) (string/longest_common_prefix.hpp)
• Suffix Array / 接尾辞配列 ($O(N (\log N)^2)$, Manber & Myers) (string/suffix_array.hpp)

.

• template.cpp

utils

• a binary search / 二分探索 (utils/binary_search.hpp)
• a binary search on floating point numbers / 二分探索 (浮動小数点数) (utils/binary_search_float.hpp)
• utils/binary_search_max.hpp
• utils/coordinate_compression.hpp
• DSU on tree (sack) (utils/dsu_on_tree.hpp)
• upward fast zeta transform on primes (utils/fast_zeta_transform.hpp)
• map from disjoint intervals (utils/interval_map.hpp)
• set of disjoint intervals (utils/interval_set.hpp)
• Length of Left-to-right Maxima (前処理 $O(n \log n)$ + $O(1)$) (utils/left_to_right_maxima.hpp)
• utils/macros.hpp
• Minimum Excluded Value ($O(n)$ for a given sorted container) (utils/mex.hpp)
• utils/mex_calculator.hpp
• utils/mo_algorithm.hpp
• utils/next_combination.hpp
• 2-SAT ($O(N)$) (utils/two_satisfiability.hpp)

Verification Files

data_structure

• data_structure/binary_indexed_tree.test.cpp
• data_structure/convex_hull_trick.line_add_get_min.test.cpp
• data_structure/dual_segment_tree.range_update_query.test.cpp
• data_structure/dynamic_connectivity_offline.dynamic_graph_vertex_add_component_sum.test.cpp
• data_structure/euler_tour_subtree_query.vertex_add_subtree_sum.test.cpp
• data_structure/lazy_propagation_red_black_tree.range_affine_range_sum.test.cpp
• data_structure/lazy_propagation_segment_tree.range_affine_range_sum.test.cpp
• data_structure/lazy_propagation_segment_tree.range_min_range_add.test.cpp
• data_structure/li_chao_tree.segment_add_get_min.test.cpp
• data_structure/link_cut_tree.dynamic_tree_vertex_add_path_sum.test.cpp
• data_structure/link_cut_tree.dynamic_tree_vertex_set_path_composite.test.cpp
• data_structure/link_cut_tree.marked_ancestor.test.cpp
• data_structure/link_cut_tree.vertex_add_path_sum.test.cpp
• data_structure/link_cut_tree.vertex_set_path_composite.test.cpp
• data_structure/segment_tree.point_add_range_sum.test.cpp
• data_structure/segment_tree.point_set_range_composite.test.cpp
• data_structure/segment_tree.range_sum_query.test.cpp
• data_structure/segment_tree_beats.DSL_2_F.test.cpp
• data_structure/segment_tree_beats.DSL_2_G.test.cpp
• data_structure/segment_tree_beats.DSL_2_H.test.cpp
• data_structure/segment_tree_beats.DSL_2_I.test.cpp
• data_structure/segment_tree_beats.yosupo.test.cpp
• data_structure/sliding_window_aggregation.yosupo.test.cpp
• data_structure/sparse_table.yosupo.test.cpp
• data_structure/sparse_table.yukicoder-1036.test.cpp
• data_structure/union_find_tree.aoj.test.cpp
• data_structure/union_find_tree.yosupo.test.cpp
• data_structure/wavelet_matrix.aoj2674.test.cpp
• data_structure/wavelet_matrix.range_kth_smallest.test.cpp
• data_structure/wavelet_matrix.rectangle_sum.test.cpp

graph

• graph/bellman_ford.test.cpp
• graph/cartesian_tree.yosupo.test.cpp
• graph/cartesian_tree.yukicoder-1031.test.cpp
• graph/dijkstra.yukicoder-1065.test.cpp
• graph/functional_graph.yuki1254.test.cpp
• graph/kruskal.aoj.test.cpp
• graph/lowest_common_ancestor.aoj.test.cpp
• graph/lowest_common_ancestor.yosupo.test.cpp
• graph/strongly_connected_components.yosupo.test.cpp
• graph/tree_decomposition.aoj_2405.test.cpp
• graph/yen_algorithm.yukicoder-1069.test.cpp

hack

• hack/fastio.yosupo.test.cpp
• hack/fastio_scanner_and_printer.yosupo.test.cpp

modulus

• modulus/choose.yukicoder-1035.test.cpp
• modulus/formal_power_series.exp.test.cpp
• modulus/formal_power_series.inv.test.cpp
• modulus/formal_power_series.log.test.cpp
• modulus/formal_power_series.yukicoder-1145.test.cpp
• modulus/mint_with_zero.test.cpp
• modulus/modlog.yosupo.test.cpp
• modulus/modlog.yuki1255.test.cpp
• modulus/modsqrt.yosupo.test.cpp
• modulus/number_theoretic_transformation.yosupo.test.cpp
• modulus/number_theoretic_transformation_with_garner.yosupo.test.cpp
• modulus/stirling_number_of_the_second_kind_convolution.yosupo.test.cpp
• modulus/twelvefold_way.balls_and_boxes_1.test.cpp
• modulus/twelvefold_way.balls_and_boxes_10.test.cpp
• modulus/twelvefold_way.balls_and_boxes_11.test.cpp
• modulus/twelvefold_way.balls_and_boxes_2.test.cpp
• modulus/twelvefold_way.balls_and_boxes_3.test.cpp
• modulus/twelvefold_way.balls_and_boxes_4.test.cpp
• modulus/twelvefold_way.balls_and_boxes_5.test.cpp
• modulus/twelvefold_way.balls_and_boxes_6.test.cpp
• modulus/twelvefold_way.balls_and_boxes_7.test.cpp
• modulus/twelvefold_way.balls_and_boxes_8.test.cpp
• modulus/twelvefold_way.balls_and_boxes_9.test.cpp

number

• number/fast_fourier_transformation.yukicoder-856.test.cpp
• number/matrix.yukicoder-1073.test.cpp
• number/matrix_template.yukicoder-1073.test.cpp
• number/primes.aoj.test.cpp
• number/primes.yukicoder-1140.test.cpp
• number/primes_extra.yukicoder-1659.test.cpp

old

• old/rollback-square-decomposition.yukicoder-1031.test.cpp

string

• string/longest_common_prefix.yosupo.test.cpp
• string/suffix_array.yosupo.test.cpp

utils

• utils/binary_search.aoj.test.cpp
• utils/dsu_on_tree.aoj.test.cpp
• utils/mo_algorithm.yuki1270.test.cpp
• utils/two_satisfiability.yosupo.test.cpp