appendix.md

Appendix / FAQ

Environments

• Do not use the macro beginning with ATCODER_.
• Although we aimed to make it work in many environments, it requires some C++ extension. We assume the following.
  • __int128 / unsigned __int128(g++, clang++) or _mul128 / _umul128(Visual Studio) works.
  • __builtin_(ctz/ctzll/clz/clzll/popcount)(g++, clang++) or _BitScan(Forward/Reverse)(Visual Studio) works.
  • char / short / int / ll and their unsigned types (and signed char) are 8 / 16 / 32 / 64 bits.
  • 💻 Signed integers are two's complement.

How to Install

g++ / clang++

The easiest way is to put atcoder folder in the same place as main.cpp and execute g++ main.cpp -std=c++14 -I ., as noted in the index. Here, . is the symbol that represents the current directory (you should type a space and a period after I).

If you don't want to copy atcoder folder manually, do as follows.

• Specify the command like g++ main.cpp -std=c++14 -I /path/to/ac-library (/path/to/ac-library stands for the directory where the downloaded ac-library is located).
• Specify the place of atcoder folder by the environment variable CPLUS_INCLUDE_PATH as CPLUS_INCLUDE_PATH="/path/to/ac-library". (On Windows, type like C:\path\to\ac-library in the field of the variable CPLUS_INCLUDE_PATH on the Window of Environment Variables. Note that, you should use backslashes, not slashes.) Then, you can compile just by g++ main.cpp -std=c++14.

Visual Studio

Visual Studio 2019 / 2022 is supported. Update it if you are using old Visual Studio.

If Visual Studio is installed, there is a folder like the following.

• C:\Program Files\Microsoft Visual Studio\2022\(Community, Professional or Enterprise)\VC\Tools\MSVC\(Some number, e.g. 14.35.32215)\include
• C:\Program Files (x86)\Microsoft Visual Studio\2019\(Community, Professional or Enterprise)\VC\Tools\MSVC\(Some number, e.g. 14.27.29110)\include

Copy atcoder folder into it, i.e., put it so that the path will be as follows.

• C:\Program Files\Microsoft Visual Studio\2022\(Community, Professional or Enterprise)\VC\Tools\MSVC\(Some number, e.g. 14.35.32215)\include\atcoder\dsu.hpp

How to Submit to Other Online Judge Systems

We prepared the script expander.py (python3.5 or later). The code combined.cpp, which can be compiled on other online judge systems, is generated by executing python3 expander.py main.cpp.

Although we tested it, we do not guarantee that it works correctly.

Preliminaries

💻Mark

This mark represents that the part, e.g., modint, may be difficult to use if you do not know much about C++. AC Library is designed to be still usable if you ignore the parts with this mark.

Template Function

For example, suffix_array(v) can take vector<int>, vector<ll>, et cetera as an argument. In this document, we unify these notations to suffix_array<T>(vector<T> v).

For example, to calculate the suffix array of the integral array $v$ stored in vector<int>, we can code as follows.

vector<int> sa = suffix_array(v);
// vector<int> sa = suffix_array<int>(v); : wrong usage

Default Constructor

The structs like scc_graph can be declared not only like the former code, but also like the latter code without initialization.

#include <atcoder/scc>;
using namespace atcoder;

int main() {
    int n;
    scanf("%d", &n);
    scc_graph g(n); // create the graph with n vertices
    return 0;
}

#include <atcoder/scc>;
using namespace atcoder;

scc_graph g;

int main() {
    return 0;
}

If it is declared in the latter way, the behavior (of the default constructor) is as follows.

• It takes $O(1)$-time.
• The behavior is undefined if the member variables are accessed or the member functions are called.

You can also assign a value to the struct later.

#include <atcoder/scc>;
using namespace atcoder;

scc_graph g;

int main() {
    g = scc_graph(10);
    return 0;
}

The Type of the Edges

In the graph libraries, the type mf_graph<Cap>::edge is used to store edges.

For example, the type of the edges of mf_graph<int> is mf_graph<int>::edge. If you are not familiar to ::, you can use the string mf_graph<int>::edge in the same manner as int or string, like the following example.

vector<mf_graph<int>::edge> v;
mf_graph<int>::edge e;

Default Template Arguments

Sometimes the following notation is used, as in the document of convolution.

vector<T> convolution<int m = 998244353>(vector<T> a, vector<T> b)

It means the default template argument. As the following example, you can call the function without explicitly specifying m.

vector<long long> c = convolution(a, b);
vector<long long> c = convolution<924844033>(a, b);

In the first case, $m$ is automatically set to be $998244353$. In the second case, $m$ becomes the value that is explicitly specified, which is $924844033$ here.

💻 explicit specifier

Constructors of structs except modint are declared with the explicit specifier.

Precise requirements in Segtree / LazySegtree

In some situations, the cardinality of algebraic structures for Segtree / LazySegtree would be infinite. In precise meaning, it may break the constraints in the document.

For example, for the typical LazySegtree on $S = \mathrm{int}$ that processes the queries of range max and range addition, $S$ is not closed under addition due to the overflow. To resolve this problem, it is ensured to work correctly in the following situation.

Segtree

• $S$ is an algebraic structure that satisfies the properties in the document.
• $e \in S' \subseteq S$
• If the arguments and the results are in $S'$, the types and operations work correctly.
• For any moment, every contigurous subsequence $a_l, a_{l+1}, \cdots, a_{r-1}$ satisfies $a_l \cdot a_{l+1} \cdot \ldots \cdot a_{r-1}\in S'$.

LazySegtree

• $(S, F)$ is a pair of algebraic structures that satisfies the properties in the document.
• $e \in S' \subseteq S, \mathrm{id} \in F' \subseteq F$
• If the arguments and the results are in $S'$ or $F'$, the types and operations work correctly.
• For any moment, every contigurous subsequence $a_l, a_{l+1}, \cdots, a_{r-1}$ satisfies $a_l \cdot a_{l+1} \cdot \ldots \cdot a_{r-1}\in S'$.
• Let us fix an element and denote the maps acted on it by $f_0, f_1, ..., f_{k-1} \in F$ in this order. Then, for every contigurous subsequence $f_l, \cdots, f_{r-1}$, $f_{r-1} \circ f_{l+1} \circ \dots \circ f_{l} \in F'$.

Above LazySegtree can naturally be defined as follows, using infinite algebraic structures $S$ and $F$.

• $S = \mathbb{Z} \cup {-\infty}$
• The binary operation $\cdot$ on $S$ is $\mathrm{max}$ and $e = -\infty$.
• $F$ is the set of the maps that adds a constant integer ($\mathrm{id}$ is the map that adds $0$).

Under some sufficiently small constraints, it can be treated by this library by setting $(S', F')$ as follows.

• $S' = (\mathbb{Z} \cap (-2^{31}, 2^{31})) \cup {-\infty}$
• $S'$ is represented by $\mathrm{int}$. The element $x\in S'$ is represented as $x$ in $\mathrm{int}$ if $x \neq -\infty$ and $-2^{31}$ if $x = -\infty$.
• $F'$ is the set of the maps that adds a constant integer in $[-2^{31}, 2^{31})$ and represented naturally using the type $\mathrm{int}$.

The Behavior of maxflow

Internally, for each edge $e$, it stores the flow amount $f_e$ and the capacity $c_e$. Let $\mathrm{out}(v)$ and $\mathrm{in}(v)$ be the set of edges starts and ends at $v$, respectively. For each vertex $v$, let $g(v, f) = \sum_{e \in \mathrm{in}(v)}{f_e} - \sum_{e \in \mathrm{out}(v)}{f_e}$.

flow(s, t)

It changes the flow amount of each edge. Let $f_e$ and $f'_e$ be the flow amount of edge $e$ before and after calling it, respectively. Precisely, it changes the flow amount as follows.

• $0 \leq f'_e \leq c_e$
• $g(v, f) = g(v, f')$ holds for all vertices $v$ other than $s$ and $t$.
• If flow_limit is specified, $g(t, f') - g(t, f) \leq \mathrm{flow\_limit}$.
• $g(t, f') - g(t, f)$ is maximized under these conditions. It returns this $g(t, f') - g(t, f)$.

min_cut(s)

The residual network is the graph whose edge set is given by gathering $(u, v)$ for each edge $e = (u, v, f_e, c_e)$ with $f_e \lt c_e$ and $(v, u)$ for each edge $e$ with $0 \lt f_e$. It returns the set of the vertices that is reachable from $s$ in the residual network.

change_edge(i, new_cap, new_flow)

It changes the flow amount and the capacity of the edge $i$ to new_flow and new_cap, respectively. It doesn't change other values.