Atcoder 算法库（ACL） 出了快一年了，一直没仔细看，这两天写 《天才算法少女》 的主线剧情，正好复习一下这个。不过这玩意更新的着实挺慢的，还没我的 Template 算法多。。。不过至少可以和 rng_58 学习一下怎么写 test 。。。
首先讲一下怎么像 STL 一样加入 cpp 的默认头文件，方法当然是编辑编译器的 Search directories。这个库结构非常简单，对于不支持 ACL 的 OJ，估计也可以手动展开一下。
例题
为了推广这个库，rng_58 还准备了两场 ACL contest，用来测试模板。当然这个东西的适用范围还有待观察，毕竟模板的缺点是不能进去魔改，最典型的缺陷可能就是无法给 std::set<int> 里的二叉树节点加卫星数据 size 以实现求第 kth 大这种实用操作。。。？。。。（比如需要加卫星数据的并查集可能也没法搞了）
A – Disjoint Set Union
并查集
– https://vjudge.net/problem/AtCoder-abc181_f
B – Fenwick Tree
树状数组
C – Floor Sum
等差数列每一项除以 M 下取整的和。（这玩意居然也需要进模板？）
$$\sum_{i = 0}^{N – 1} \lfloor(A \times i + B) / M\rfloor$$
D – Maxflow
最大流
– https://vjudge.net/problem/AtCoder-agc038_f
– https://atcoder.jp/contests/arc107/tasks/arc107_f
– https://atcoder.jp/contests/abc193/tasks/abc193_f
import sys
from atcoder.maxflow import MFGraph
I = lambda: [int(x) for x in input().split()]
n, m = I()
s = 2*n
t = s+1
G = MFGraph(t+1)
a = I()
b = I()
z = 0
for i in range(n):
bb = abs(b[i])
z += bb
G.add_edge(i, i+n, a[i] + bb)
bb *= 2
if (b[i] < 0):
G.add_edge(i+n, t, bb)
else:
G.add_edge(s, i, bb)
for i in range(m):
x, y = I()
x -= 1
y -= 1
G.add_edge(x+n, y, sys.maxsize)
G.add_edge(y+n, x, sys.maxsize)
print(z-G.flow(s,t))
E – MinCostFlow
最小费用最大流
– https://atcoder.jp/contests/agc034/tasks/agc034_d
F – Convolution
FFT 卷积
G – SCC
强连通分量
H – Two SAT
2SAT
I – Number of Substrings
后缀数组
里面的实现用的是 sa-is 线性构造算法。
– https://atcoder.jp/contests/abc141/submissions/23884310
– https://atcoder.jp/contests/arc097/tasks/arc097_a
J – Segment Tree
线段树
K – Range Affine Range Sum
懒标记线段树
L – Lazy Segment Tree
懒标记线段树
