AT 板子库（未来遗产类）

· · 个人记录

看起来非常好用啊！

请引用头文件 <atcoder/all> ，显然只有在 atcoder 能用。

要 using namespace atcoder

并查集

限制：n\leq10^8,u,v\in [0,n)

dsu A(n)

定义一个点数为 n，标号为 [0,n) 的并查集。

O(n)

A.merge(u,v)

合并两个点。

返回一个 int ，若 u,v 在同一个连通块，则返回所在连通块的代表点，否则返回新连通块的代表点。

均摊 \alpha(n)

A.same(u,v)

查询两个点是否在同一个点集。

返回一个 bool。

均摊 \alpha(n)

A.leader(u)

查询点所在连通块的代表点。

返回一个 int。

均摊 \alpha(n)

A.size(u)

查询点所在连通块的大小。

返回一个 int。

A.groups()

查询连通块情况。

返回一个 vector<vector<int>>，其中每个 vector<int> 是一个连通块。

树状数组

限制：n\leq10^8,l,r,x\in [0,n)

fenwick_tree<Type> T(n)

定义一个长度为 n，标号为 [0,n)，类型为 Type 的树状数组。其中 Type\in \{int,uint,ll,ull,modint\}，关于 modint，详情见后面。

O(n)

T.add(x,k)

在 x 处单点加 k。

没有返回值。

O(\log n)

T.sum(l,r)

求位置 [l,r) 处的和。

返回一个 Type。

O(\log n)

基础类欧几里得

floor_sum(n,m,a,b) 求 \sum\limits_{i=0}^{n-1}\lfloor\frac{ai+b}{m}\rfloor。

最大流

mf_graph<int>G(n) 定义一张点数为 n，编号为 [0,n) 的网络。

G.add_edge(u,v,w) 加入一条起点为 u，终点为 v，流量上限为 w 的弧。

G.flow(s,t) 求源点为 s，汇点为 t 的最大流，会对下面边集中的边当前流量进行更改。

G.edges()，得到一个应该是 vector<edge> 的东西？正常用的时候可以直接用 auto E=G.edges() 和 for(auto e:E) 调用所有网络中的边。e 有参数 e.from,e.to,e.flow，分别表示边的起点，终点和当前流量。

最小费用最大流

mcf_graph<int,int>G(n) 定义一张点数为 n，编号为 [0,n) 的网络。

G.add_edge(u,v,w,c) 加入一条起点为 u，终点为 v，流量上限为 w，单位流量代价为 c 的弧。

G.flow(s,t) 求源点为 s，汇点为 t 的最小费用最大流，返回一个 pair ，第一个元是最大流，第二个元是最小费用。

G.edges()，同最大流。