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: Template21
      fname: template.cpp
- name: Miscellaneous Algorithms
  dir: misc/
  files:
    - title: Convex Hull Trick
      fname: ConvexHullTrick.cpp
    - title: Dynamic Convex Hull Trick
      fname: DynamicConvexHullTrick.cpp
    - title: Isotonic Regression
      fname: IsotonicRegression.cpp
      desc: Given a DAG $G=(V,E)$ on $\vert V\vert=n$ vertices and initial values $a_1,a_2,\dots,a_n$ on vertices, find $b_1,b_2,\dots,b_n$ satisfying $b_u\geq b_v$ iff $(u,v)\in E$ and minimize $\sum\limits_{i=1}^{n}\vert b_i-a_i\vert$
    - title: Matroid Intersection
      fname: MatroidIntersection.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: Weighted Matroid Intersection
      fname: WeightedMatroidIntersection.cpp
      desc: Find the maximum weighted common independent set of two matroids. Matroids are given by independence oracle.
    - title: Multiple Knapsack
      fname: MultipleBackpack.cpp
      desc: Solve the knapsack problem with multiple items of each kind in $O(nW)$, optimized using monotone deque.
    - title: Nim Multiplication
      fname: NimMultiplication.cpp
      desc: Multiplication of nimbers
    - title: Simplex Algorithm
      fname: Simplex.cpp
      desc: Simplex algorithm for solving linear programs. Maximize $cx$ subject to $Ax\leq b$. Input format given in the code.
    - title: SlopeTrick
      fname: SlopeTrick.cpp
    - title: Gosper's Hack
      fname: Subset.cpp
      desc: Find all subsets of $S$ in $O(2^{\vert S\vert})$/ all subsets of size $k$ of $S$ in $O(\binom{\vert S\vert}{k})$.
    - title: Surreal Number
      fname: SurrealNumber.cpp
      desc: Calculation of surreal number in partizan games(with numbers only, e.g., $\star$ is not allowed).
    - title: Zeller's Formula
      fname: whatday.cpp
      desc: Determine the day of the week given the date.
- name: String
  dir: string/
  files:
    - title: Knuth-Morris-Pratt algorithm
      fname: KMP.cpp
    - title: Z-function
      fname: Z.cpp
      desc: compute LCP of every suffix and the originals string in $O(n)$ time
    - title: Manacher algorithm
      fname: manacher.cpp
    - title: Aho-corasick automaton
      fname: ACAM.cpp
    - title: Trie
      fname: Trie.cpp
    - title: Suffix array
      fname: SA.cpp
      desc: Suffix array construction in $O(n\log{n})$ time
    - title: SAIS
      fname: SAIS.cpp
      desc: Linear-time algorithm for suffix array construction
    - title: Suffix automaton
      fname: SAM.cpp
    - title: Generalized suffix automaton
      fname: GSAM.cpp
    - title: PAM
      fname: PAM.cpp
      desc: Palindromic automaton
    - title: Minimum Representation
      fname: MinRot.cpp
      desc: Find $i$ such that $s_i s_{(i+1)\mod n}\cdots s_{(i+n-1)\mod n}$ is lexicographically minimum in $O(n)$
    - title: Lyndon Decomposition
      fname: Duval.cpp
      desc: Find the lyndon decomposition of a given string in $O(n)$ time
- name: Math
  dir: math/
  files:
    - title: Modular Arithmetic
      fname: Mod.cpp
      desc: Some basic operations
    - title: Berlekamp-Massey algorithm
      fname: Berlekamp-Massey.cpp
    - title: BigIntegers
      fname: BigNum.cpp
    - title: Chinese Remainder Theorem
      fname: CRT.cpp
    - title: Matrix Determinant
      fname: Determinant.cpp
    - title: DIVCNT1
      fname: DIVCNT1.cpp
      desc: Let $d_1(n)$ be the number of divisors of $n$. Calculate $\sum\limits_{i=1}^{n}d_1(n)$ in $O(n^{1/3}\log{n})$ time.
    - title: (Quasi-)Euclidean algorithm
      fname: Euclid.cpp
      desc: $f(n)=\sum\limits_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor$\\ $g(n)=\sum\limits_{i=0}^{n}i\cdot \lfloor\frac{ai+b}{c}\rfloor$\\ $h(n)=\sum\limits_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor^2$.
    - title: Linear sieve
      fname: EulerSieve.cpp
    - title: Extended Lucas Theorem
      fname: ExtLucas.cpp
      desc: Calculate $\binom{n}{k}\mod m$ for $m\leq 10^6$
    - title: Farey Series
      fname: Farey.cpp
    - title: Fast modular arithmetics
      fname: FastMultiplication.cpp
    - title: Fast Fourier Transform(FFT)
      fname: FFT.cpp
    - title: Fast Walsh-Hadamard Transform(FWT)
      fname: FWT.cpp
    - title: Number Theoretic Transform(NTT)
      fname: NTT.cpp
    - title: Gaussian Elimination
      fname: GaussJordan.cpp
    - title: Jiangly's Polynomial Operations
      fname: jly.cpp
    - title: Lagrange Interpolation
      fname: Interpolation.cpp
    - title: Linear Basis
      fname: LinearBasis.cpp
    - title: System of equations with linear congruence
      fname: LinearCongruence.cpp
    - title: Matrix Operations
      fname: Matrix.cpp
    - title: Pollard-Rho factorization with Miller-Rabin Primality test
      fname: PollardRho.cpp
    - title: Pell's equation
      fname: Pell.cpp
      desc: Minimal positive integer solution to the equation $x^2-ny^2=1$.
    - title: Pohlig-Hellman algorithm
      fname: PohligHellman.cpp
      desc: Given prime(cyclic group) $p$ and primitive root(generator) $g$ and a number $0\leq x\leq p-1$, find the discrete logarithm of $x$, i.e., $0\leq i\leq p-1$ such that $x^i\equiv 1\pmod p$. Works efficient when $p-1$ factorizes well. 
    - title: Matrix operations
      fname: Matrix.cpp
    - title: Points In A Circle
      fname: PIAC.cpp
      desc: Calculate the number of integer points inside a circle of radius $r$ centered at the origin.
    - title: Polynomial Operations
      fname: PolyOp.cpp
    - title: Fast Lagrange Interpolation
      fname: PolySum.cpp
    - title: Power Tower
      fname: PowerTower.cpp
      desc: Given $a_1,\dots,a_n$, calculate $\text{pow}(a[l],\text{pow}(a[l+1],\text{pow}(\dots,a[r])))$.
    - title: Counting the number(polynomial) of primes
      fname: PrimeCount.cpp
      desc: Let $f(x)$ be any polynomial, calculate $\sum\limits_{p\leq n\atop{p\text{ prime}}}f(p)$ in $O(\frac{\sqrt{n}}{\log{n}}\cdot \text{deg}(f))$ time, assuming the point evaluation of $f$ can be done in $O(1)$ and prefix sum can be calculated in $O(\text{deg}(f))$.
    - title: Primitive Root
      fname: PrimitiveRoot.cpp
    - title: Schreier-Sims algorithm
      fname: SchreierSims.cpp
      desc: Given some permutations $P=\{p_1,p_2,\dots,p_m\}$, calculate the number of elements in the group generated by $P$.
    - title: Segment Sieve
      fname: SegmentSieve.cpp
    - title: Simpson's algorithm
      fname: Simpson.cpp
    - title: Stirling number of the first kind
      fname: StirlingI.cpp
    - title: Stirling number of the second kind(multiple)
      fname: StirlingIIM.cpp
    - title: Stirling number of the first kind(single)
      fname: StirlingIIS.cpp
    - title: Subset convolution
      fname: SubsetConvolution.cpp
      desc: Given $f,g:2^{n}\rightarrow \{0,1\}$, calculate $f\circ g(s)=\sum\limits_{s'\subseteq s}f(s')g(s\setminus s')$ in $O(2^n\cdot n^2)$.
    - title: Prefix Sum of Phi
      fname: SumPhi.cpp
    - title: Prefix Sum of Mu
      fname: SumMu.cpp
    - title: Tonelli-Shanks algorithm
      fname: TonelliShanks.cpp
      desc: Given $x,p$, determine if $x$ is a quadratic residue modulo $p$, if yes, return $0<y<p$ such that $y^2\equiv x\pmod p$.
    - title: Count Paths in Young's Tableaux
      fname: Young.cpp
      desc: Given a Young's Tableaux with $n$ rows and row lengths $a_0,a_1,\dots,a_n$, count the number of paths from $(0,0)$ to each grid in the last row. Call solve $(a,a[n-1],\textsf{way})$ to find the answer where \textsf{way} is a vector of size $n+1$ with only first entry equal to $1$ and all other are zeroes.
- name: Graph Theory
  dir: graph/
  files:
    - title: Dijkstra's algorithm(priority queue)
      fname: DijkstraI.cpp
    - title: Dijkstra's algorithm(brute force)
      fname: DijkstraII.cpp
    - title: Floyd-Warshall algorithm
      fname: FloydWarshall.cpp
    - title: SPFA
      fname: SPFA.cpp
    - title: Prim's algorithm(priority queue)
      fname: PrimI.cpp
    - title: Prim's algorithm(brute force)
      fname: PrimII.cpp
    - title: Kruskal's algorithm
      fname: Kruskal.cpp
    - title: Maximum Matching for bipartite graphs
      fname: BipartiteMatching.cpp
    - title: Lexicographical minimum maximum partial transversal
      fname: LexicoMin.cpp
    - title: Maximum Matching for general graphs
      fname: CommonMatching.cpp
    - title: Hopcroft-Karp algorithm(faster bipartite matching)
      fname: HopcroftKarp.cpp
    - title: Kuhn-Munkres algorithm(minimum weight bipartite matching)
      fname: KuhnMunkres.cpp
    - title: Dinic's algorithm
      fname: Dinic.cpp
    - title: Minimum-cost flow(nonnegative weights)
      fname: MinCostFlow.cpp
    - title: Minimum-cost flow(supports negative weights)
      fname: MinCostFlow(SPFA).cpp
    - title: Gomory-Hu Tree
      fname: GomoryHuTree.cpp
    - title: Edge coloring for bipartite graphs
      fname: BipartiteEdgeColoring.cpp
      desc: Edge coloring for bipartite graphs(using $\Delta$ colors where $\Delta$ is the maximum degree) in $O(\vert V\vert^2)$ time.
    - title: Block Cut Tree
      fname: BlockCutTree.cpp
    - title: Bridge Tree
      fname: BridgeTree.cpp
    - title: Chordal Graph
      fname: ChordalGraph.cpp
      desc: Compute the perfect elimination order(PEO) of a chordal graph.
    - title: Dominator Tree
      fname: DominatorTree.cpp
    - title: Dynamic Connectivity
      fname: DynamicConnectivity.cpp
      desc: Maintains the connectivity information upon edge additions and deletions(offline), runs in $O(\vert E\vert\log{\vert E\vert})$ time.
    - title: Dynamic Bridge
      fname: DynamicBridge.cpp
      desc: Maintains the bridge information upon edge additions and deletions(offline), runs in $O(\vert E\vert\log{\vert E\vert})$ time. 
    - title: Ear Decomposition
      fname: EarDecomposition.cpp
    - title: Eulerian Path
      fname: Eulerian.cpp
    - title: Kosaraju's algorithm
      fname: Kosaraju.cpp
    - title: Lowest Common Ancestor(with binary lifting)
      fname: LCA.cpp
    - title: Lowest Common Ancestor(with range minimum query)
      fname: LCArmq.cpp
    - title: Minimum spanning arborescence
      fname: MinimumArborescence.cpp
      desc: Chu-Liu algorithm, implemented in $O(\vert V\vert^2)$ time.
    - title: Minimum Diameter Spanning Tree
      fname: MinimumDiameterSpanningTree.cpp
    - title: Tarjan's algorithm
      fname: Tarjan.cpp
    - title: Number of cycles of length $3$
      fname: TriangleCount.cpp
      desc: returns the number of cycles of length $3$ in the graph in $O(\vert E\vert\sqrt{\vert E\vert})$ time.
    - title: Number of cycles of length $4$
      fname: SquareCount.cpp
      desc: returns the number of cycles of length $4$ in the graph in $O(\vert E\vert\sqrt{\vert E\vert})$ time.
    - title: Chain Intersection on Tree
      fname: TreeChainIntersection.cpp
      desc: Computes the intersection of two chains on a tree(also a chain).
    - title: Centroid Decomposition
      fname: CentroidDecomposition.cpp
    - title: Heavy-Light Decomposition
      fname: HLD.cpp
    - title: Long Chain Decomposition
      fname: LSD.cpp
    - title: Virtual Tree
      fname: VirtualTree.cpp
- name: Data Structures
  dir: ds/
  files:
    - title: Sparse Table
      fname: SparseTable.cpp
    - title: Fenwick tree 
      fname: BIT.cpp
    - title: Cartesian tree
      fname: DescartesTree.cpp
    - title: Disjoint Set Union
      fname: DSU.cpp
    - title: Li Chao Segment Tree
      fname: LichaoSegmentTree.cpp
      desc: Given a set $S$ containing function of the same ``type" (e.g. lines, $y=ax+b$). The type of function need to have the \textbf{transcending property} (will be explained later). Supports two type of queries\begin{itemize} \item Add a function to $S$\item Answer the maximum/minimum value at $x=t$ considering all functions in $S$\end{itemize} A type of function has \textbf{transcending property} if given two functions $f(x),g(x)$ of that type, if $f(t)$ is greater than/smaller than $g(t)$ for some $x=t$, then $f(x)$ will be greater than/smaller than $g(x)$ for $x>t$. In other words, once $f(x)$ "win/lose" $g(x)$, $f(x)$ will continue to "win/lose" $g(x)$.
    - title: Link-Cut Tree
      fname: LCT.cpp
    - title: Monotone Deque
      fname: MonotoneDeque.cpp
      desc: Given an array $a_1,\dots,a_n$ and an interger $k\leq n$, computes $b_1,\dots,b_{n-k+1}$ in $O(n)$ time, where $b_i=\min\limits_{j=i}^{i+k-1}a_j$ for each $1\leq i\leq n-k+1$.
    - title: Monotone Stack
      fname: MonotoneStack.cpp
      desc: Given an array $a_1,\dots,a_n$, for each $1\leq i\leq n$, computes the first integer smaller than it before/after it in $O(n)$ time. 
    - title: Persistent Disjoint Set Union
      fname: PersistentDSU.cpp
    - title: Persistent Segment Tree
      fname: PersistentSegmentTree.cpp
    - title: Persistent Trie
      fname: PersistentTrie.cpp
    - title: Mo's algorithm
      fname: Mo.cpp
      desc: Block size should be set as $O(\sqrt{n})$. Runs in $O(n\sqrt{n}\cdot f(x))$ time, where $f(x)$ is the running time per update/delete operation.
    - title: Mo's algorithm with rollback
      fname: RollbackMo.cpp
      desc: Delete function can be implemented in a rollback manner. Block size should be set as $O(\sqrt{n})$. Runs in $O(n\sqrt{n}\cdot f(x))$ time, where $f(x)$ is the running time per update/delete operation.
    - title: Mo's algorithm on tree
      fname: TreeMo.cpp
      desc: Block size should be set as $O(\sqrt{n})$. Runs in $O(n\sqrt{n}\cdot f(x))$ time, where $f(x)$ is the running time per update/delete operation.
    - title: Mo's algorithm with queries
      fname: QMo.cpp
      desc: Block size should be set as $O(n^{2/3})$. Runs in $O(n^{5/3}\cdot f(x))$ time, where $f(x)$ is the running time per update/delete operation.
    - title: Mo's algorithm on tree with queries
      fname: QTreeMo.cpp
      desc: Block size should be set as $O(n^{2/3})$. Runs in $O(n^{5/3}\cdot f(x))$ time, where $f(x)$ is the running time per update/delete operation.
    - title: Big Integers
      fname: BigInt.cpp
      desc: Using segment tree to efficiently maintain big integers under single addition/removal update under certain base
    - title: Segment Tree Beats
      fname: SegmentTreeBeats.cpp
      desc: Segment trees that support interval $x=\max(x,a)$ operation, runs in $O(q\log{n})$ amortized time.
    - title: Segment Tree Merge
      fname: SegmentTreeMerge.cpp
      desc: Given a tree of $n$ vertices and $a_1,a_2,\dots,a_n$, for each $1\leq i\leq n$ compute how many $a_j<a_i$ where $j$ is in the subtree of $i$. Runs in $O(n\log{n})$ time.
    - title: Treap
      fname: Treap.cpp
    - title: DSU on tree
      fname: TreeDSU.cpp
    - title: Young's Tableaux
      fname: Young.cpp
      desc: Maintains information for longest increasing subsequence(LIS) of some array. The length of first $k$ rows is the maximum length of $k$-LIS(maximum length of $k$ disjoint LISs) of the array. \textbf{Note} that the first $k$ rows are't necessarily the $k$-LIS itself. 
- name: Geometrics
  dir: geo/
  files:
    - title: 2D geometric template
      fname: Basics.cpp
    - title: 3D geometric template
      fname: Stereometry.cpp
    - title: jly's template
      fname: jly.cpp
- name: Appendices
  dir: appendix/
  files:
    - title: Slime Trick
      fname: Slime.tex
    - title: Stack Trick
      fname: Stack.tex
    - title: From static sets to expandable sets
      fname: Set.tex
    - title: Combinatorics Formulas
      fname: Combinatorics.tex
    - title: Generating Functions
      fname: GF.tex