AC Library

AC Library is the official library of AtCoder, specifically designed for competitive programming. Its primary goal is to provide a high-quality, bug-free collection of algorithms that can be used with minimal effort by AtCoder users.

Key Design Principles:

• Optimized for Competitive Programming: The library intentionally prioritizes convenience in a competitive programming context over standard C++ best practices. For example, it uses int instead of size_t, and Segtree handles function pointers rather than functional objects.
• Stability: The project focuses on collecting issues, recording changelogs, and versioning releases rather than frequent feature additions.

For detailed technical documentation of specific algorithms, refer to the AC Library Document (English).

The two_sat class is used to solve 2-Satisfiability (2-SAT) problems. Given $N$ variables $x_0, x_1, ext{--}, x_{N-1}$, you can add clauses of the form $(x_i = f) ext{ or } (x_j = g)$ and determine if there exists a truth assignment that satisfies all clauses.

Workflow

1. Initialize: Create a two_sat object with $n$ variables.
2. Add Constraints: Use add_clause to add logical OR constraints.
3. Check Satisfiability: Call satisfiable() to check if a valid assignment exists.
4. Retrieve Assignment: If satisfiable() returned true, call answer() to get the boolean values for each variable.

The dsu class implements a Disjoint Set Union (also known as Union-Find) data structure for undirected graphs. It allows you to:

• Add edges between vertices.
• Determine if two vertices are in the same connected component.

Operations are performed in amortized $O(\alpha(n))$ time, where $\alpha$ is the inverse Ackermann function.

A lazy_segtree is a data structure designed for a Monoid $(S, ext{op}, e)$ and a set of mappings $F$ from $S$ to $S$ that satisfy the following conditions:

• $F$ contains the identity mapping $\text{id}$ (where $\text{id}(x) = x$ for all $x \in S$).
• $F$ is closed under composition (for any $f, g \in F$, $f \circ g \in F$).
• For any $f \in F$ and $x, y \in S$, $f(x \cdot y) = f(x) \cdot f(y)$ (the mapping distributes over the monoid operation).

It allows you to perform the following operations in $O(\log N)$ time:

• Apply a mapping $f \in F$ to all elements in a range $[l, r)$.
• Retrieve the product (monoid operation result) of elements in a range $[l, r)$.

Note: The complexity assumes that the oracle functions (op, e, mapping, composition, id) run in constant time. If they run in $O(f(n))$, the overall complexity is scaled by $O(f(n))$.

The segtree (Segment Tree) is a data structure designed for use with a Monoid $(S, ext{op}, e)$. A Monoid must satisfy:

• Associativity: $(a ext{ op } b) ext{ op } c = a ext{ op } (b ext{ op } c)$ for all $a, b, c ext{ in } S$.
• Identity Element: $a ext{ op } e = e ext{ op } a = a$ for all $a ext{ in } S$.

For an array of length $n$, it allows:

• Point updates (changing a single element) in $O( ext{log } n)$.
• Range product queries (calculating the product of elements in a range) in $O( ext{log } n)$.

Note: The complexity assumes the operations op and e run in constant time. If they run in $O(f(n))$, all complexities are scaled by $f(n)$.

A Fenwick Tree (Binary Indexed Tree) is a data structure that allows you to perform two operations on an array of length $n$ in $O(\log n)$ time:

1. Point Update: Add a value to a specific element.
2. Range Sum: Calculate the sum of elements in a given interval $[l, r)$.

Note that the sum operation uses a half-open interval $[l, r)$, meaning it calculates the sum from index $l$ up to $r-1$.

The mf_graph implementation stores flow $f_e$ and capacity $c_e$ for each edge.

flow(s, t)

Updates the flow amount of each edge to maximize the net flow from $s$ to $t$ (subject to capacity constraints and flow conservation at all vertices except $s$ and $t$). If a flow_limit is specified, it ensures the increase in flow at $t$ does not exceed that limit.

min_cut(s)

Returns the set of vertices reachable from $s$ in the residual network.

change_edge(i, new_cap, new_flow)

Directly updates the capacity and flow of the $i$-th edge without affecting other edges.

When using the AC Library, keep the following conventions and behaviors in mind:

• Undefined Behavior: Behavior is undefined if inputs are provided outside of the specified constraints.
• Mathematical Conventions: $0^0$ is defined as $1$.
• Graph Inputs: Unless explicitly stated otherwise, multiple edges and self-loops are allowed in graph inputs.
• Type Shorthand: In documentation, long types are often abbreviated:
  • unsigned int $\rightarrow$ uint
  • long long $\rightarrow$ ll
  • unsigned long long $\rightarrow$ ull

A lazy_segtree is a data structure designed to handle a monoid $(S, ext{op}, e)$ and a set of mapping functions $F$ (where each $f ext{ is } S o S$). It allows for efficient interval updates and interval queries.

To use it, your mapping functions $F$ must satisfy:

1. Identity: $F$ contains an identity map $\mathrm{id}$ such that $\mathrm{id}(x) = x$.
2. Closure: $F$ is closed under composition ($f \circ g \in F$).
3. Distributivity: $f(x \cdot y) = f(x) \cdot f(y)$ for all $f \in F$ and $x, y \in S$.

It supports two main operations in $O(\log N)$ time:

• Acting a map $f \in F$ on all elements in an interval.
• Calculating the product (monoid operation) of elements in an interval.

The scc_graph class calculates the strongly connected components (SCC) of a directed graph.

An SCC is a maximal set of vertices where every vertex is reachable from every other vertex in the set. The scc() method returns the components as a list of vertex lists, where:

• Each vertex belongs to exactly one component.
• The components themselves are returned in topological order. This means if there is a directed path from a vertex in component $A$ to a vertex in component $B$, then component $A$ will appear before component $B$ in the resulting list.
• The order of vertices within each individual component list is undefined.