Procon

log K’s Procon Library

log K / lX57 が競技プログラミングで使用しているライブラリです。

---

使用方法

各ライブラリのドキュメントには以下の情報が含まれています：

• 概要: ライブラリの説明
• 関数/メソッド: 使用可能な関数やメソッドの詳細
• 制約: 入力の制約条件
• 計算量: 時間計算量と空間計算量

コード例

各ライブラリは #include でインクルードして使用します：

#include "Library/DataStructure/SegmentTree.hpp"

---

命名規則

本ライブラリでは以下の命名規則を採用しています：

• クラス名: PascalCase (例: SegmentTree)
• メソッド名: PascalCase (例: Build, Product)
• 関数名: PascalCase (例: InputTree, CalculateTreeDepth)
• 変数名（private）: snake_case with trailing underscore (例: size_, data_)
• パラメータ名: snake_case (例: merge, zero_index)

ただし、次の例外規則を設けています。

• グラフ : G
• グラフ $G$ の頂点数 : V
• 列の長さ : N
• 十分大きな定数 : inf

---

注意事項

• すべてのライブラリは C++17 以降での使用を想定しています。
• テンプレート化されているクラスについて、typename に用いている特定の名称の意味は次の通りです。
  • Arithmetic : int long long mint などの四則演算が可能な整数型を想定しています。
  • Ordered : int long long などの四則演算と大小比較が可能な整数型を想定しています。

---

ライセンス

このライブラリは競技プログラミングでの使用を目的として作成されています。

Library Files

Library

• Library/Common.hpp
• Library/Template.hpp
• Library/TemplateExtend.hpp
• modint (Library/modint.hpp)
• Library/origin.cpp

Library/DataStructure

• Library/DataStructure/CumulativeSum2D.hpp
• Dual Segment Tree - 双対セグメント木 (Library/DataStructure/DualSegmentTree.hpp)
• Library/DataStructure/FenwickTree.hpp
• Lazy Segment Tree - 遅延評価セグメント木 (Library/DataStructure/LazySegmentTree.hpp)
• Library/DataStructure/MergeSortTree.hpp
• Library/DataStructure/RollbackUnionFind.hpp
• Segment Tree - セグメント木 (Library/DataStructure/SegmentTree.hpp)
• Sparse Table (Library/DataStructure/SparseTable.hpp)
• Library/DataStructure/UnionFind.hpp
• Library/DataStructure/WeightedUnionFind.hpp

Library/Graph

• Library/Graph/BellmanFord.hpp
• Library/Graph/CycleDetection.hpp
• Library/Graph/Dijkstra.hpp
• Graph - グラフ構造 (Library/Graph/Graph.hpp)
• Library/Graph/GraphUtilities.hpp
• Library/Graph/Kruskal.hpp
• Library/Graph/LowLink.hpp
• Library/Graph/StronglyConnectedComponents.hpp
• Library/Graph/WarshallFloyd.hpp

Library/Math

• Library/Math/MillerRabin.hpp
• Library/Math/Montgomery.hpp
• Library/Math/SternBrocotTree.hpp

Library/Other

• Library/Other/Compress.hpp
• Longest Increasing Subsequence - 最長増加部分列 (Library/Other/LongestIncreasingSubsequence.hpp)

Library/String

• Library/String/Trie.hpp
• Library/String/ZAlgorithm.hpp

Library/Tree

• Library/Tree/HeavyLightDecomposition.hpp
• Library/Tree/LowestCommonAncestor.hpp
• Library/Tree/RerootingDP.hpp
• Library/Tree/Tree.hpp
• Library/Tree/TreeDiameter.hpp
• Library/Tree/tmp.hpp

Library/unauthenticated

• Library/unauthenticated/AuxiliaryTree.hpp
• Combination - 組合せ (Library/unauthenticated/Combination.hpp)
• Erasable Priority Queue - 消せる Priority Queue (Library/unauthenticated/ErasablePriorityQueue.hpp)
• Functional Graph (Library/unauthenticated/FunctionalGraph.hpp)
• Graph Template - グラフテンプレート (Library/unauthenticated/GraphTemplate.hpp)
• 0-1 Knapsack - 0-1 ナップザック問題 (Library/unauthenticated/Knapsack01.hpp)
• Library/unauthenticated/KthMultiSet.hpp
• Longest Distance - DAGにおける最長距離 (Library/unauthenticated/LongestDistance.hpp)
• Library/unauthenticated/Manacher.hpp
• Matrix - 行列演算 (Library/unauthenticated/Matrix.hpp)
• Mo's Algorithm (Library/unauthenticated/Mo.hpp)
• Rolling Hash - ローリングハッシュ (Library/unauthenticated/RollingHash.hpp)
• Slide-Min - スライド最小値 (Library/unauthenticated/SlideMin.hpp)

Verification Files

verify

• verify/AOJ-0560.test.cpp
• verify/AOJ-0723.test.cpp
• verify/AOJ-ALDS1-7-A.test.cpp
• verify/AOJ-DSL-1-A.test.cpp
• verify/AOJ-DSL-1-B.test.cpp
• verify/AOJ-DSL-2-A.test.cpp
• verify/AOJ-DSL-2-B.test.cpp
• verify/AOJ-DSL-2-G.test.cpp
• verify/AOJ-DSL-5-B.test.cpp
• verify/AOJ-GRL-1-A.test.cpp
• verify/AOJ-GRL-1-B.test.cpp
• verify/AOJ-GRL-1-C.test.cpp
• verify/AOJ-GRL-3-A.test.cpp
• verify/AOJ-GRL-3-B.test.cpp
• verify/AOJ-GRL-3-C.test.cpp
• verify/AOJ-GRL-4-A.test.cpp
• verify/AOJ-GRL-5-A.test.cpp
• verify/AOJ-GRL-5-B.test.cpp
• verify/AOJ-GRL-5-C.test.cpp
• verify/LC-CycleDetection.test.cpp
• verify/LC-CycleDetectionUndirected.test.cpp
• verify/LC-JumponTree.test.cpp
• verify/LC-LongestIncreasingSubsequence.test.cpp
• verify/LC-LowestCommonAncestor-HLD.test.cpp
• verify/LC-LowestCommonAncestor.test.cpp
• verify/LC-MinimumSpanningTree.test.cpp
• verify/LC-PersistentUnionfind.test.cpp
• verify/LC-PointAddRangeSum-FenwickTree.test.cpp
• verify/LC-PointAddRangeSum.test.cpp
• verify/LC-PointSetRangeComposite.test.cpp
• verify/LC-PrimalityTest.test.cpp
• verify/LC-RangeAddRangeMin.test.cpp
• verify/LC-RangeAffinePointGet.test.cpp
• verify/LC-RangeAffineRangeSum.test.cpp
• verify/LC-RectangleSum.test.cpp
• verify/LC-ShortestPath.test.cpp
• verify/LC-StaricRMQ.test.cpp
• verify/LC-StaticRangeSumWithUpperBound.test.cpp
• verify/LC-StronglyConnectedComponents.test.cpp
• verify/LC-TreeDiameter.test.cpp
• verify/LC-TreePathCompositeSum.test.cpp
• verify/LC-Unionfind.test.cpp
• verify/LC-UnionfindWithPotential.test.cpp
• verify/LC-VertexAddPathSum.test.cpp
• verify/LC-VertexAddSubtreeSum.test.cpp
• verify/LC-VertexSetPathComposite.test.cpp