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

懒标记线段树