実装は基本的に実装テンプレートをベースに実装してます。
実装テンプレート
高速I/O処理
最大公約数 ((拡張)ユークリッドの互除法)
繰り返し二乗法
線分同士の交差判定
凸包 (Graham Scan)
座標圧縮
素集合データ構造 (Union-Find)
Leftist Heap
Pairing Heap
Rank-Pairing Heap
永続RBST
Splay tree
Red-Black Tree
AA Tree
Left-Leaning Red-Black Tree
AVL Tree
Weak AVL Tree
Binary Indexed Tree
Range Minimum Query (セグメント木)
Range Sum Query (動的セグメント木)
RMQ and RSQ (遅延評価セグメント木)
RMQ and RUQ (遅延評価セグメント木)
histric maximal valueのRMQ (遅延評価セグメント木)
区間chminクエリ, RMQ, and RSQ (Segment tree beats)
区間chmin/chmaxクエリ, RMQ, RSQ, RAQ, RUQ (Segment tree beats)
線分追加クエリ, 線分加算クエリ (遅延評価 Li-Chao (Segment) Tree, 動的セグ木)
線分追加クエリ, RAQ, RMQ (遅延評価 Li-Chao (Segment) Tree, 動的セグ木)
Link-Cut Tree
Sliding Window Minimum
Convex Hull Trick (Li-Chao (Segment) Tree)
Convex Hull Trick (Li-Chao (Segment) Tree, 動的セグ木)
Convex Hull Trick (Deque)
kd-tree (2次元)
単一始点最短経路 (ダイクストラ法, 二分ヒープ)
単一始点最短経路 (ダイクストラ法, フィボナッチヒープ)
単一始点最短経路 (ダイクストラ法, Radix Heap)
強連結成分分解 (Kosaraju’s Algorithm)
橋検出 (Path-based DFS)
関節点検出 (LowLink)
Dominator (Lengauer-Tarjan Algorithm)
Dominator (SEMI-NCA Algorithm)
重心分解
最小共通祖先 (ダブリング)
Auxiliary Tree (LCAベース)
最大フロー (Dinic’s Algorithm)
最大フロー (Push-Relabel Algorithm, highest selection)
最小費用流問題 (Primal Dual Algorithm)
きたまさ法
Fast Modulo Transform
Rolling Hash
Suffix Array (Manber and Myers Algorithm)
Aho-Corasick Algorithm
戻る