utils/macros.hpp

• View this file on GitHub
• Last update: 2019-12-20 06:12:24+09:00
• Include: #include "utils/macros.hpp"

Required by

• Binary Indexed Tree (data_structure/binary_indexed_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_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)
• Wavelet Matrix (data_structure/wavelet_matrix.hpp)
• Bellman-Ford algorithm (graph/bellman_ford.hpp)
• Cartesian tree ($O(n)$) (graph/cartesian_tree.hpp)
• graph/connected_components.hpp
• Eulerian cycle (無向, 復元) (graph/euler_graph.hpp)
• graph/format.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)
• 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)
• topological sort (graph/topological_sort.hpp)
• graph/transpose_graph.hpp
• 木分解 (木幅 $t \le 2$) (graph/tree_decomposition.hpp)
• 虚樹 / virtual trees (graph/virtual_trees.hpp)
• the Bell number (前処理 $O(NK)$ + $O(1)$) (modulus/bell_number.hpp)
• combination / 組合せ ${} _ n C _ r$ (愚直 $O(r)$) (modulus/choose_simple.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)
• discrete log / 離散対数 (the baby-step giant-step, $O(\sqrt{m})$) (modulus/modlog.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)
• 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/matrix_template.hpp
• FFT convolution (number/fast_fourier_transformation.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
• 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)
• a binary search on floating point numbers / 二分探索 (浮動小数点数) (utils/binary_search_float.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)
• Length of Left-to-right Maxima (前処理 $O(n \log n)$ + $O(1)$) (utils/left_to_right_maxima.hpp)
• 2-SAT ($O(N)$) (utils/two_satisfiability.hpp)

Verified with

• data_structure/binary_indexed_tree.test.cpp
• data_structure/convex_hull_trick.line_add_get_min.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/wavelet_matrix.aoj2674.test.cpp
• data_structure/wavelet_matrix.range_kth_smallest.test.cpp
• data_structure/wavelet_matrix.rectangle_sum.test.cpp
• 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
• 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/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/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/rollback-square-decomposition.yukicoder-1031.test.cpp
• string/longest_common_prefix.yosupo.test.cpp
• string/suffix_array.yosupo.test.cpp
• 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

Code

#pragma once
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)

#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)

Back to top page