これはなに

まぐげんがーの競プロライブラリです。

構造

C++

• graph

  • Graph.hpp （ダイクストラとかBFSとかをやる）
  • SCC.hpp （強連結成分分解）-> よくわからないのでACLを使いましょう
  • LCA.hpp （最小共通祖先 / Lowest Common Ancestor）

• heuristic

  • Randint.hpp （std::mt19937を使った乱数生成）
  • Timer.hpp（std::chronoを使った時間計測）

• io

  • FastIO.hpp（readとputchar_unlockedを使った高速入出力 std::cin, std::coutのおよそ2~5倍の実行速度）

• math

  • Argsort.hpp （偏角ソートをするときにstd::sortに渡す関数）
  • Combination.hpp （nCr, nPr, nHrなどを前計算ありO(1)で求める）
  • DivisorList.hpp （約数列挙。返り値はstd::vector<T>型）
  • ModInt.hpp （※Integers.hppに移動しました modint。ACLの方が高性能）
  • PrimeFactor.hpp （素因数分解。O(sqrt(N))）
  • PrimeFactorPollard.hpp （ポラードのρ法を使った素因数分解。補助関数としてIP (is_prime), PM (pow_mod)がある）

• other

  • Integers.hpp （符号あり128bit整数のラッパーcent_tとi8 ~ i64, u8 ~ u64を定義 + modint）

  • others.hpp （競プロ用のテンプレート。includeのテンプレ、マクロ、デバッグとか）

  • gridtoInt.hpp （グリッドに数字を割り振る便利関数。後でothers.hppに統合するかも？）

• structure

  • BinaryIndexedTree.hpp （BIT / Fenwick tree。0-Indexed。）
  • CompressVec.hpp （std::vectorを渡すと座標圧縮してくれる）
  • Cumsum.hpp （累積和）
  • RollingHash.hpp （ローリングハッシュ。法はデフォルトが1e9 + 7、好きな数にもできる）
  • SegmentTree.hpp （セグメント木。struct{ using valueType = SomeType; static SomeType op(SomeType a, SomeType b){}; static inline SomeType id{}; }みたいな構造体でモノイドを定義してる）
  • Trie.hpp （Trie木 / Prefix Tree）
  • UndoUnionFind.hpp （操作取消可能UF。再帰数え上げの時とかに使う。）
  • UnionFind.hpp （ユニオンファインド。groups()もある。）
  • WeightedUnionFind.hpp （重み付きUF。）

C++以外の言語のライブラリ→コンテストで使ったことがないので正しく動くかどうかの保証がありません