scl.yaml

- name: General
  dir: general/
  files:
    - title: Code library checksum
      fname: checksum.py
    - title: Makefile
      fname: Makefile.txt
    - title: .vimrc
      fname: vimrc.txt
    - title: Stack
      fname: stack.cpp
    - title: Template
      fname: template.cpp
- name: Miscellaneous Algorithms
  dir: misc/
  files:
    - title: 2-SAT
      fname: two-sat.cpp
      usage:
        init(n): Initialize the solver with $n$ variables.
        add_clause(x, xval, y, yval): Add a clause \lstinline|(x == xval) -> (y == yval)|.
        solve(): Solve the problem. Return the satisfiability of the problem.
        operator[](i): Get the value of $i$-th variable.
    - title: Matroid Intersection
      fname: matint.cpp
      desc: Find the maximum cardinality common independent set of two matroids. Matroids are given by independence oracle.
      usage:
          MatroidOracle: The independence oracle maintaining an independent set. \textbf{Note} that the default constructor must properly initialize inner state to an empty set.
          insert(x): Insert element labeled $x$ to the independent set.
          test(x): Test whether the set is still independent if $x$ is inserted.
          MatroidIntersection<MT1, MT2>(n): Construct the matroid intersection solver with $n$ elements labeled from 0 and matroid oracles \lstinline|MT1| and \lstinline|MT2|.
          run(): Run the algorithm and return the matroid intersection.
    - title: Connectivity Dynamic Programming
      fname: conndp.cpp
- name: String
  dir: string/
  files:
    - title: Knuth-Morris-Pratt algorithm
      fname: kmp.cpp
    - title: Manacher algorithm
      fname: manacher.cpp
    - title: Aho-corasick automaton
      fname: aho-corasick.cpp
    - title: Trie
      fname: trie.cpp
    - title: Suffix array
      fname: sa.cpp
      desc: The character immediately after the end of the string \textbf{MUST} be set to the \textbf{UNIQUE} \textbf{SMALLEST} element.
      usage: 
        s[]: the source string
        sa[i]: the index of starting position of $i$-th suffix
        rk[i]: the number of suffixes less than the suffix starting from $i$
        h[i]: the longest common prefix between the $i$-th and $(i-1)$-th lexicographically smallest suffixes
        n: size of source string
        m: size of character set
    - title: Rolling hash
      fname: hasher.cpp
      desc: \textbf{PLEASE} call \lstinline|init_hash()| in \lstinline{int main()}!
      usage:
        build(str): Construct the hasher with given string.
        operator()(l, r): Get hash value of substring $[l, r)$.
- name: Math
  dir: math/
  files:
    - title: Extended Euclidean algorithm and Chinese remainder theorem
      fname: crt.cpp
      desc: |
        Solve $ax + by = g = \gcd(a,b)$ w.r.t. $x, y$. \par
        If $(x_0, y_0)$ is an integer solution of $ax + by = g = \gcd(x,y)$, then every integer solution of it can be written as $(x_0 + kb', y_0 - ka')$, where $a' = a/g$, $b' = b/g$, and $k$ is arbitrary integer. \par
    - title: Linear basis
      fname: linearbasis.cpp
    - title: Gauss elimination over finite field
      fname: gauss.cpp
    - title: Berlekamp-Massey algorithm
      fname: berlekamp-massey.cpp
      desc: |
        Call \lstinline|berlekamp()| with input sequence $(x_0, x_1, \cdots, x_{n - 1})$. Return a vector of coefficients $(c_0 = 1, c_1, \cdots, c_{m-1})$ with minimum $m$, such that $\sum_{i=0}^m c_i x_{j-i} = 0$ for all possible $j$.
    - title: Fast Walsh-Hadamard transform
      fname: fwt.cpp
    - title: Fast fourier transform
      fname: fft.cpp
    - title: Number theoretic transform
      fname: ntt.cpp
    - title: Sieve of Euler 
      fname: euler_sieve.cpp
    - title: Sieve of Euler (General)
      fname: euler_sieve_mult.cpp
    - title: Miller-Rabin primality test
      fname: miller-rabin.cpp
      desc: |
        The array \lstinline|a[]| (excluding senitel, i.e. \lstinline|LLONG_MAX|) should be
        
        \begin{tabular}{p{6cm} p{5cm}}
          \lstinline|{2}| & when $n < 2,047$. \\
          \lstinline|{2, 7, 61}| & when $n < 4,759,123,141$ ($2^{32}$) . \\
          \lstinline|{2, 3, 5, 7, 11}| & when $n < 2.1 \times 10^{12}$. \\
          \lstinline|{2, 325, 9375, 28178, 450775, 9780504, 1795265022}| & when $n < 2^{64}$.
        \end{tabular} 
    - title: Integer factorization (Pollard's rho)
      fname: pollard-rho.cpp
    - title: Adaptive Simpson's Method
      fname: simpson.cpp
      desc: The Simpson's formula has order 3 algebraic precision.
      usage:
        integrate(l, r, eps, est, fn): Integrate the function \lstinline|fn| on interval $[l, r]$. \lstinline|eps| is the estimated precision, while \lstinline|est| is the current estimation, which can be set to arbitrary value initially.
    - title: Linear Programming (Simplex)
      fname: lpsolver.cpp
      desc: |
        This function solves the following linear program
          \begin{align*}
            \max \qquad & c^{\top} x \\
            \text{s.t.} \qquad & Ax \leq b \\
            & x \geq 0
          \end{align*}
        If the program is infeasible, \lstinline{NAN} is returned; if the program is unbounded, \lstinline{DBL_MAX} is returned; otherwise, the optimal target is returned and the arguments are stored in \lstinline{x}.
- name: Graph Theory
  dir: graph/
  files:
    - title: Strongly connected components
      usage:
        dfs(u): Run \lstinline|dfs(u)| for each unlabelled vertex.
        scc[i]: The vertices of the $i$-th scc.
        sccid[u]: The index of the scc that contains $u$.
        contract(): Compute the contracted graph.
      fname: scc.cpp
    - title: Vertex biconnected components, cut vertex
      fname: bcc.cpp
      desc: A component root $u$ is a cut vertex iff the size of \lstinline|bccin[u]| is at least 2; for any other vertice $u$, it is a cut vertex iff \lstinline|bccin[u]| is nonempty.
      usage:
        dfs(u): Run \lstinline|dfs(u)| for each connected component.
        bcc[i]: The edges of the $i$-th biconnected components, numbered from 0. If the bcc is a simple cycle, the edges are sorted in order.
        bccin[u]: The indices of biconnected components reachable from vertex $u$.
    - title: Minimum spanning arborescence, faster
      fname: msa.cpp
      desc:  All vertices are 1-based. Clear the fields when reuse the struct.
      usage: 
        add_edge(u, v, w): Add an edge from $u$ to $v$ with weight $w$.
        run(n, rt): Compute the total weight of MSA rooted at \lstinline|rt|. If not exist, retun \lstinline|LLONG_MIN|.
      time: $O(|E| \log^2 |V|)$ 
    - title: Minimum spanning arborescence, slow
      fname: msa-n2.cpp
      desc:  All vertices are 1-based. Clear the fields when reuse the struct.
      usage: 
        init(n): Initalize the structure with $n$ vertices, indexed from 1.
        add_edge(u, v, w): Add an edge from $u$ to $v$ with weight $w$.
        run(n, rt): Compute the total weight of MSA rooted at \lstinline|rt|. If not exist, retun \lstinline|LLONG_MIN|.
      time: $O(|V|^2)$ 
    - title: Maximum flow (Dinic)
      fname: dinic.cpp
      usage: 
        add_edge(u, v, c): Add an edge from $u$ to $v$ with capacity $c$.
        max_flow(s, t): Compute maximum flow from $s$ to $t$.
      time:  For general graph, $O(V^2E)$; for network with unit capacity, $O(\min\{V^{2/3}, \sqrt{E}\}E)$; for bipartite network, $O(\sqrt{V}E)$.
    - title: Maximum cardinality bipartite matching (Hungarian)
      fname: hungarian.cpp
    - title: Maximum matching of general graph (Edmond's blossom)
      fname: blossom.cpp
      usage:
          init(n): Initialize the template with $n$ vertices, numbered from 1.
          add_edge(u, v): Add an undirected edge $uv$.
          solve(): Find the maximum matching. Return the number of matched edges.
          mate[]: The mate of a matched vertex. If it is not matched, then the value is 0.
      time: $O(|V|^3)$, but extremely fast in practice.
    - title: Minimum cost maximum flow
      fname: mcmf.cpp
#    - title: Global minimum cut (Stoer-Wagner)
#      fname: stoer.cpp
#      usage:
#          stoer(w) : Compute the global minimum cut of the graph specified by the \textbf{symmetric} adjacenct matrix \lstinline|w| (0-based). Return the capaity of the cut and the indices of one part of the cut.
#      time: $O(|V|^3)$
    - title: Fast LCA, Virtual Tree
      fname: vtree.cpp
      desc: All indices of the tree are 1-based.
      usage: 
        prep(): Initialization.
        lca(u, v): Query the lowest common ancestor of $u$ and $v$.
        vtree(vs): Create virtual tree with vertex set \lstinline|vs|.
    - title: Heavy-light decomposition
      fname: hldecmp.cpp
      time: The decomposition itself takes linear time. Each query takes $O(\log n)$ operations.
    - title: Centroid decomposition
      fname: centdecomp.cpp
      desc: |
        Note that the centroid here is not the exact centroid of the graph. It only guarantees that the size of each subtree does not exceed half of that of the original tree. This is enough to guarantee the correct time complexity. All vertices are numbered from 1.
        Call \lstinline|decomp(root)| to use.
      usage:
        decomp(u, p): Decompose the tree rooted at $u$ with parent $p$.
      time: The decomposition itself takes $O(n \log n)$ time.
    - title: DSU on tree
      fname: dsu.cpp
      desc: |
        This implementation avoids parallel existence of multiple data structures but requires that the data structure is invertible.
        To use this template, implement \lstinline|merge|, \lstinline|enter|, \lstinline|leave| as needed;
        first call \lstinline|decomp(root, 0)|, then call \lstinline|work(root, 0, false)|. Labels of vertices start from 1.
      usage:
        decomp(u, p): Decompose the tree $u$.
        work(u, p, keep): Work for subtree $u$. When \lstinline|keep| is set, information is not cleared.
      time: $O(n \log n)$ times the complexity for \lstinline|merge|, \lstinline|enter|, \lstinline|leave|.
- name: Data Structures
  dir: ds/
  files:
    - title: Fenwick tree (point update range query)
      fname: bit_purq.cpp
    - title: Fenwick tree (range update point query)
      fname: bit_rupq.cpp
    - title: Segment tree
      fname: segtree.cpp
    - title: Mo's algorithm
      fname: mo.cpp
      desc: |
        All intervals are closed on both sides. When running functions \lstinline|enter()| and \lstinline|leave()|, the global $l$ and $r$ has not changed yet. \textbf{Assume the data structure is initialized for empty interval}.
      usage:
        add_query(id, l, r): Add id-th query $[l, r]$.
        run(): Run Mo's algorithm.
        yield(id): \textbf{TODO}. Yield answer for id-th query.
        enter(o): \textbf{TODO}. Add o-th element.
        leave(o): \textbf{TODO}. Remove o-th element.
    - title: Mo's algorithm on tree
      fname: mo_tree.cpp
      desc: Numbers of vertices are 1-based. Implement \lstinline|deal(int u)| and \lstinline|query::yield()|.
    - title: Treap
      fname: treap.cpp
      desc: Self-balanced binary search tree which supports split and merge.
      usage: 
        push(x): Push lazy tags to children.
        pull(x): Update statistics of node $x$.
        Init(x, v): Initialize node $x$ with value $v$.
        Add(x, v): Apply addition to subtree $x$.
        Reverse(x): Apply reversion to subtree $x$.
        Merge(x, y): Merge trees rooted at $x$ and $y$. Return the root of new tree.
        Split(t, k, x, y): Split out the left $k$ elements of tree $t$. The roots of left part and right part are stored in $x$ an d $y$, respectively.
        init(n): Initialize the treap with array of size $n$.
        work(op, l, r): Range operation over $[l, r)$.\
      time: Expected $O(\log n)$ per operation.
    - title: Link/cut tree
      fname: lct.cpp
      desc: Dynamic connectivity of undirected acyclic graph. Support single-vertex update, path aggregation and relative LCA query. Vertices are numbered from 1. Zero initialization is enough except for the statistic information.
      usage:
        pull(x): Update statistics of node $x$.
        Root(u): Get the root of tree where vertex $u$ is in.
        Link(u, v): Link two unconnected trees.
        Cut(u, v): Cut an existent edge.
        Query(u, v): Path aggregation.
        Update(u, x): Single point modification.
        LCA(u, v, root): Get the lowest common ancestor of $u$ and $v$ in tree rooted at \lstinline|root|.
      time: $O(\log n)$ per operation
    - title: Balanced binary search tree from \lstinline|pb_ds|
      fname: ordertree.cpp
    - title: Persistent segment tree, range k-th query
      fname: persistent_segtree.cpp
    - title: Block list
      fname: block.cpp
      desc:  All indices are 0-based. All ranges are left-closed right-open.
      usage:
          block::fix(): Apply tags to the current block.
          Init(l, r): Range initializer.
          Reverse(l, r): Reverse the range.
          Add(l, r, x): Add $x$ to the range.
          Query(l, r): Range aggregation.
    - title: Persistent block list
      fname: persistent_block.cpp
      desc: |
        Block list that supports persistence. All indices are 0-based. All ranges are left-closed right-open. \lstinline|std::shared_ptr| is used to ease memory management. One should modify the constructor of \lstinline|block| to maintain extra information. Here we use this policy that the size of each block does not exceed \lstinline|BLOCK|, while the sum of sizes of two adjacent blocks does not less than \lstinline|BLOCK|. 

        When some operation that breaks block list property, please call \lstinline|maintain| in time to restore the property.
      usage: 
        maintain(): Maintain the block list property.
        split(pos): Split the block list at position \lstinline|pos|. Returns an iterator to a block starting at \lstinline|pos|.
        sum(l, r): An example function of list traversal between $[l, r)$.
      time: When \lstinline|BLOCK| is properly selected, the time complexity is $O(\sqrt{n})$ per operation.
    - title: Sparse table, range minimum query
      fname: rmq.cpp
      desc: The array is 0-based and the range is left-closed right-open.
- name: Geometrics
  dir: geo/
  files:
    - title: 2D geometric template
      fname: 2dgeotemp.cpp
- name: Appendices
  dir: appendix/
  files:
    - title: Number theory
      fname: nt.tex
    - title: Burnside's lemma and Polya's enumeration theorem
      fname: burnside.tex
    - title: Supnick TSP
      fname: supnick_tsp.tex
    - title: Lagrange's interpolation
      fname: lagrange.py
      desc: |
        For sample points $(x_0, y_0), \cdots, (x_k, y_k)$, define 
        $$l_j(x) = \prod_{0 \leq m \leq k, m \neq j} \frac{x - x_m}{x_j - x_m}$$
        then the Lagrange polynomial is
        $$L(x) = \sum_{j=0}^k y_j l_j(x). $$
        
        To use the script below, type two lines
        \begin{verbatim}
                x0 x1 x2 ... xn
                y0 y1 y2 ... yn        
        \end{verbatim}
        the script will print the fractional coefficient of the polynomial in ascending exponent order.
    - title: LP duality
      fname: lp.tex