专栏文章

AtCoder Library 入门教程

DDr1fty
科技·工程参与者 12已保存评论 12

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
12 条
当前快照
1 份
快照标识符
@miqrii2e
此快照首次捕获于
2025/12/04 09:33
3 个月前
此快照最后确认于
2025/12/04 09:33
3 个月前
查看原文

简介

AtCoder Library 是 AtCoder 官方对于算法竞赛中常见的一些模板进行编写，整合成了一个库。在参与 AtCoder 的比赛时可以直接使用（当然在其他 OJ 上也可以用，只不过你需要手动将文件里代码粘贴到你的代码前端）。
以下我们只介绍 C++ 中的 AtCoder Library，python 玩家请自行去网上查阅资料。
下文中所有代码都可以通过编译（编译器：G++ 9.3.0；编译选项：-static -std=c++14 -Wall -Wl,--stack=1024000000；操作系统：Windows 10）。
官方有入门文档，但是只有日文和英文版本的，于是在此写一篇中文的介绍。
请确保你的编译器版本支持 C++14 标准。

配置

这里给出两个下载地址：AtCoder 官方 ∣\mid AtCoder - Github（建议使用第一个链接）。下过来解压，会发现有一个 python 文件，不用管。C++ 的引用都在 /atcoder 文件夹里，你可以把这个文件夹拖到编译器的 /include 目录下，这样以后在写代码的时候就可以直接 #include <atcoder/all> 来引入了。
注意，封装的所有功能和类都在 namespace atcoder 中。如果你懒得写 atcoder:: 请记得 using namespace atcoder;。

使用

AtCoder Library 总共有 1111 个小的功能集合，分别封装了树状数组，线段树，带标记的线段树，SCC 相关，字符串相关，取模意义下的整数，并查集，最大/最小流，卷积，数学相关，2-SAT。
下面会选一些有用的介绍。

树状数组

Note：感觉不如手写。没有线性建树的功能，差评。
你可以通过 fenwick_tree <T> tr(int n); 来创建一个长度为 nn 的树状数组。下标从 00 开始，初值全为 00，T 为任意整型。
支持单点加：void tr.add(int x, T d); 需要保证 0≤x<n0\le x < n 否则行为未定义。
支持区间查：T tr.sum(int l, int r); 需要保证 0≤l≤r<n0\le l \le r < n 否则行为未定义。
以上操作时间复杂度显然均为 O(log⁡n)O(\log n)。

并查集

Note：好用的，α(n)\alpha(n) 的复杂度，比 log⁡n\log n 确实要快些。
你可以通过 dsu d(int n) 来创建一个 nn 个节点，名为 d 的并查集，下标从 00 开始，时间复杂度 Θ(n)\Theta(n)。
CPP
int d.merge(int a, int b); // 加入一条边 (a, b) 并返回合并后联通块的 father
bool d.same(int a, int b); // 判断 (a, b) 是否在同一连通块
int d.leader(int a); // 找出祖先（有路径压缩）
int d.size(int a); // 给出 a 联通块的大小
以上操作都有 O(α(n))O(\alpha(n)) 的时间复杂度，同时均需要保证 0≤a,b<n0\le a,b < n。
我们还有：
CPP
vector <vector <int> > d.groups();
上面的函数可以返回分组后的编号，时间复杂度 O(n)O(n)。

字符串相关

求 LCP

CPP
vector,<int> lcp_array,(string s, vector <int> sa);
vector <int> lcp_array <T> (vector <T> s, vector <int> sa);
返回的 vector 中，第 i(0≤i<n)i(0\le i < n) 个元素代表 ∣LCP(s[ssai,ssai+1,…,n),s[ssai+1,ssai+1+1,…,n))∣\vert \text{LCP}(s[s_{sa_i}, s_{sa_i + 1}, \ldots, n), s[s_{sa_{i + 1}}, s_{sa_{i + 1} + 1}, \ldots, n)) \vert。
其中传入的 vector <int> sa 必须是 ss 的后缀数组。
时间复杂度 Θ(n)\Theta(n)，T 可以是任意整型。
特别地，1≤n≤1081\le n\le 10^8。

求后缀数组

CPP
vector <int> suffix_array (string s);
vector <int> suffix_array <T> (vector <T> s);
前者时间复杂度 Θ(n)\Theta(n)；后者 T 为任意整型，时间复杂度 Θ(nlog⁡M)\Theta(n\log M)，MM 为值域。
特别地，1≤n≤1081\le n\le 10^8。

求 Z 函数

CPP
vector <int> z_algorithm (string s);
vector <int> z_algorithm <T> (vector <T> s)
前者时间复杂度 Θ(n)\Theta(n)；后者 T 为任意整型，时间复杂度 Θ(nlog⁡M)\Theta(n\log M)，MM 为值域。
特别地，1≤n≤1081\le n\le 10^8。

取模意义下的整数

分为两种，分别是 static_modint 和 dynamic_modint。
以下是 static_modint 的原型。
CPP
template <int m, std::enable_if_t<1 <= m,
    void> *<unnamed> = nullptr> static_modint;
static_modint 的模数是不能改变的，四则运算都有重载（当然除法需要保证存在逆元）。static_modint 在与常规的整型运算时会强制转化导致取模过多效率变慢，可以考虑使用 static_modint <m>:: raw(int x) 来直接转化避免取模，但是要注意需要保证 0≤x<m0 \le x < m，否则这是一个 UB。
你可以通过 static_modint <m> x.pow(long long n) 来计算 xn(modm)x^n \pmod m（快速幂实现）。
你可以通过 int x.val() 来转换类型。
dynamic_modint 的用法大致与 static_modint 相同，但是多了一个动态设置模数的函数 .set_mod(int m)，感觉并没有什么用，不详细讲了。

线段树

事实上，它能干的下面的都能干。至于功能看完下面的想必也会懂的，因此这里只给一个原型，具体内容参见“带懒标记的线段树”：
CPP
segtree <S, op, e> seg (int n);
segtree <S, op, e> seg (vector <S> v);

带懒标记的线段树

Note：重型武器。使用了非递归写法，空间时间常数都很小。
你可以通过以下两种方式 O(n)O(n) 地构造一棵线段树（下标从 00 开始）：
CPP
lazy_segtree <S, op, e, F, mapping, composition, id> seg (int n);
lazy_segtree <S, op, e, F, mapping, composition, id> seg (vector<S> v);
下面逐一讲解这些模板类里面的东西。
  • S 是一个结构体，包含了所有你的标记和答案所维护的信息，常见的有区间长度和区间权值之类的东西。
  • op 是一个函数 S op(S x, S y)，等价于手写时的 push_up 函数，即合并答案的过程。
  • e 是 S 的单位元，即使得 op(e, x) == x 的一个变量。
  • F 是一个类型，包含你在修改时加入的信息（标记信息）。
  • mapping 是一个函数，S mapping(F x, S y) 用于把 xx 合并到 yy。
  • composition 是一个函数，F composition(F x, F y) 用于 xx 合并 yy，即两个标记的合并。
  • id 是 F 的单位元，即使得 composition(id, x) == x 的一个 F 类型的变量。
然后有以下函数：
  • void seg.set(int p, S x)：单点修。
  • S seg.get(int p)：单点查。
  • S seg.prod(int l, int r)：区间查。
  • S seg.all_prod() 直接查 [0,n)[0, n) 的信息，O(1)O(1)。
  • void seg.apply(int p, F f)：单点加。
  • void seg.apply(int l, int r, F f)：区间加。
还有很多神秘的线段树上二分操作，有兴趣的读者请自行搜索。
下面给出了一个使用 Atcoder Library Seg 实现的区间加区间查询线段树，作为参考。
CPP
#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;
using i64 = long long;
struct tag {
    i64 sum; int len;
    tag(i64 x = 0, int y = 1) {sum = x; len = y;}
};
tag mapping(i64 f, tag s) {return tag(s.sum + f * s.len, s.len);}
tag mergetag(tag x, tag y) {return tag(x.sum + y.sum, x.len + y.len);}
tag nom(){return tag(0, 1);} i64 p() {return 0;}
i64 mergef(i64 x, i64 y) {return x + y;}
int main() {
    cin.tie(NULL) -> sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector <tag> a(n, tag());
    for (auto & p : a) cin >> p.sum;
    atcoder::lazy_segtree <tag, mergetag, nom,
    i64, mapping, mergef, p> segtree(a);
    for (int i = 1; i <= m; i ++) {
        int op, x, y; i64 z;
        cin >> op >> x >> y;
        if (op == 2) cout << segtree.prod(x - 1, y).sum << '\n';
        else cin >> z, segtree.apply(x - 1, y, z);
    }
    return 0;
}
这个可以极大地减少码量。

卷积

头文件：#include <atcoder/convolution>
函数原型：
CPP
template <unsigned int mod = 998244353,
          class T,
          std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b);

std::vector<long long> convolution_ll(const std::vector<long long>& a,
                                      const std::vector<long long>& b);
两个函数均用于计算 (+,×)(+,\times) 卷积。即 fi=∑j=0iajbi−jf_i = \sum_{j = 0}^{i}a_jb_{i - j}。
对于前者，其中的类型 T 可以是任意具有整型性质的类，包括之前提到的 modint，mod 就是模数。该函数基于 NTT 实现，时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)，当然，模数也必须满足 NTT 对于模数的限制。具体的可以参考 OI-wiki:NTT。
对于后者你需要保证结果在 long long 范围内。

数学相关

有 ExCRT，快速幂，逆元之类的东西，类欧，用处不大。简单介绍一下 ExCRT。
CPP
typedef ll long long;
pair <ll, ll> crt (vector <ll> r, vector <ll> m)
返回的 pair 若为 (0,0)(0, 0) 则无解，否则返回 (p,q)(p, q)，pp 代表最小的解，qq 代表模数。形式化地，所有解都满足 x≡p(modq)x\equiv p\pmod q。

后记

在打 atcoder 的时候，这些库确实能够减少码量，但是不能忘了常数和调试困难。要避免对其的依赖。
也感谢不知道是哪篇题解让我知道了在 C++ 里原来也能用 ACL。
如果觉得写的不错的话，能给个赞吗 qwq。
感谢管理大大的审核，咕咕咕。

评论

共 12 条评论，欢迎与作者交流。

正在加载评论...