This code collection is maintained mainly for competitive programming, and partly for just understanding algorithms.

The greater part of this library is distributed as public domain, or licensed under either CC0 or the MIT license, whichever gives you the most rights in your legislation. Some code, however, has its specific license (usually because it is a dead copy of other library). For the details, please see the header of each file.

Currently I don't introduce any name spaces (packages) in each file. This is due to the circumstance unique to the competitive programming: one-file-per-submission. It is somewhat troublesome to manage many packages on a single file (especially when modifying inserted code). This style may change in the future, however.

On portability: I try not to abuse non-portable code though I sometimes resort to SBCL's extension and behaviour: e.g. declaration as assertion, bivalent stream, extensible sequence, sb-kernel:%vector-raw-bits and sb-c:define-source-transform. To my knowledge, every competition site adopts SBCL.

Every data structure and algorithm handles a 0-based index and a half-open interval unless otherwise noted.

• SBCL 2.0.3 (x64, linux) — AtCoder's version
• SBCL 1.5.5 (x64, linux) — yukicoder's version
• SBCL 1.4.16 (x64, linux) — CS Academy's version
• SBCL 1.3.13 (x64, linux) — CodeChef's version

• queue.lisp queue by singly-linked list
• deque.lisp double-ended queue with ring buffer
• double-stack-deque.lisp double-ended queue with two stacks
• abstract-heap binary heap for static order function
• heap.lisp binary heap for dynamic order function
• pairing-heap.lisp meldable heap (pairing heap)
• radix-heap.lisp radix heap
• abstract-bit.lisp binary indexed tree (aka Fenwick tree) on arbitrary commutative monoid
• binary-indexed-tree.lisp binary indexed tree (specialized for ordinary +)
• 2d-bit.lisp 2D binary indexed tree
• disjoint-set.lisp disjoint set by Union-Find algorithm
• persistent-disjoint-set.lisp partially persistent disjoint set by Union-Find algorithm
• ref-able-treap.lisp ordered set by treap; analogue of std::set or java.util.TreeSet
• explicit-treap.lisp ordered map by treap; analogue of std::map or java.util.TreeMap
• implicit-treap.lisp treap with implicit key
• interval-set.lisp ordered set of half-open intervals
• disjoint-sparse-table.lisp disjoint sparse table on arbitrary semigroup
• range-tree.lisp 2D range tree on arbitrary commutative monoid
• range-tree-fc.lisp 2D range tree with fractional cascading
• convex-hull-trick.lisp convex hull trick
• succinct-bit-vector.lisp three-layer succinct bit vector
• wavelet-matrix.lisp wavelet matrix (with compact bit vector)
• persistent-vector.lisp persistent vector
• dice.lisp six-sided dice

• bisect.lisp analogue of std::lower_bound and std::upper_bound
• trisect.lisp maximum (minimum) of unimodal function
• quicksort.lisp quicksort
• merge-sort.lisp merge sort
• binsort.lisp bin sort; counting sort
• map-permutations.lisp permutation and combination
• next-permutation.lisp next permutation w.r.t. lexicographical order
• mo.lisp Mo's algorithm
• inverse-table.lisp inverse lookup table of vector
• adjacent-duplicates.lisp deletion of adjacent duplicates
• map-run-length.lisp run-length encoding
• inversion-number.lisp counting inversions of vector by merge sort
• lis.lisp longest increasing subsequence
• mex.lisp minimum excludant on non-negative integers
• swag.lisp sliding window aggregation
• sliding-window.lisp sliding window minimum (or maximum)
• order-statistic.lisp expected O(n) algorithm for k-th order statistic of sequence
• symmetric-group.lisp decomposition to cyclic permutations and some operations on a symmetric group
• fkm.lisp Fredricksen, Kessler, and Maiorana algorithm
• date.lisp some utilities about date

• modular-arithmetic.lisp extended Euclidean algorithm; Bezout equation; modular inverse; discrete logarithm; Gaussian elimination
• mod-power.lisp modular exponentiation
• power.lisp exponentiation on arbitrary monoid
• binomial-coefficient-mod.lisp binomial coefficient with fixed modulus; linear-time construction of tables of inverses, factorials, and inverses of factorials
• partition-number.lisp partition number
• bounded-partition-number.lisp partition number with upper-bound
• dynamic-mod-operations.lisp addition/multiplication with dynamic modulus
• mod-operations.lisp addition/multiplication with static modulus
• eratosthenes.lisp enumeration of primes; prime factorization
• ext-eratosthenes.lisp faster prime factorization than naive trial division
• divisor.lisp enumeration of divisors
• primality.lisp primality test (Miller-Rabin)
• enum-quotients.lisp enumeration of truncated quotients
• gemm.lisp matrix multiplication over semiring
• freiwald.lisp Freiwalds' algorithm
• f2.lisp linear algebra on GF(2)
• walsh-hadamard.lisp fast Walsh-Hadamard transform
• zeta-transform.lisp fast zeta/Möbius transform
• zeta-integer.lisp fast zeta/Möbius transform w.r.t. divisors or multiples of integer
• farey.lisp Farey sequence

• fft.lisp complex FFT (radix-2)
• fft-real.lisp real FFT (radix-2)
• fft-recursive.lisp naive FFT by simple recursion
• relative-error.lisp relative error
• log-factorial.lisp logarithm of factorial (logarithm of gamma function)

• bit-basher.lisp 64-times faster operations on simple-bit-vector
• gray-code.lisp Gray code
• tzcount.lisp TZCNT operation
• logreverse.lisp bit-reversal operation

• bipartite-matching.lisp maximum bipartite matching (Ford-Fulkerson)
• hopcroft-karp.lisp maximum bipartite matching (Hopcroft-Karp)
• jonker-volgenant.lisp weighted bipartite matching (Jonker-Volgenant)
• gabow-edmonds.lisp maximum non-bipartite matching (Gabow-Edmonds)
• bipartite-p.lisp test of bipartiteness
• bron-kerbosch.lisp maximum clique
• ford-fulkerson.lisp maximum flow (Ford-Fulkerson algorithm)
• dinic.lisp maximum flow (Dinic's algorithm)
• lca.lisp lowest common anscestor (binary lifting)
• min-cost-flow.lisp minimum cost flow (SSP)
• boruvka.lisp minimum spanning tree (Borůvka's algorithm)
• topological-sort.lisp topological sort on DAG
• dfs-order.lisp Euler tour of tree
• condensation.lisp strongly connected component of directed graph (Tarjan's algorithm); 2-SAT
• block-cut-tree.lisp biconnected component of undirected graph; block-cut tree
• tree-centroid.lisp centroid decomposition of tree
• chordal-graph.lisp recognition of graph chordality (maximum cardinality search); perfect elimination order
• diameter.lisp diameter of tree
• mo-tree.lisp Mo's algorithm for paths on tree (vertex query)
• random-graph.lisp fast generation of random adjacency matrices

• complex-geometry.lisp some utilities for 2D geometry with complex number; smallest circle problem (Welzl's algorithm)
• convex-hull.lisp 2D convex hull (monotone chain algorithm)

• rolling-hash.lisp 32-bit rolling hash
• rolling-hash62.lisp 62-bit rolling hash
• 2d-rolling-hash.lisp 2D 32-bit rolling hash
• triemap.lisp map structure by Trie
• trie.lisp multiset structure by Trie
• z-algorithm.lisp Z-algorithm

• read-line-into.lisp read-line into a given string
• buffered-read-line.lisp read-line into a recycled string
• read-fixnum.lisp faster read for fixnum
• read-bignum.lisp faster read for bignum
• with-buffered-stdout.lisp buffering macro for *standard-output*

• template.lisp template code
• with-cache.lisp memoization of function
• dotimes-unroll.lisp loop unrolling
• placeholder-syntax.lisp Clojure-style placeholder syntax

• integer-pack.lisp defstruct-like macro to deal with an integer as a bundle of some slots
• increase-spase.lisp This header runs another SBCL as external process and leaves the entire processing to it. (This ugly hack was invented to increase the stack size of SBCL on contest sites.)
• compile-time-increase-space.lisp analogue of increase-space at compile time
• self-compile.lisp self-rewriting compilation