AtCoder Library（ACL） は AtCoder側で様々なアルゴリズムを実装したものです。
C++で使えます。
詳しくは以下の投稿を見てください。
この記事では、この AtCoder Library にはどのようなアルゴリズムが実装されていて、それはどのように使えばよいのか、ということを解説していきます。
なお、今回の記事では、 AtCoder Library の使い方を確認できる問題が揃えられている、
というものも用いていきます。
このコンテストは、けんちょんさん(@drken) が解説されています。
AtCoder Library は、
#include <atcoder/all>
で一括includeできます。
DSU
無向グラフにおいて、
- 辺を追加する
- 2頂点が連結化を判定する
処理を、ならし$O(\alpha (n))$ で行えます。
また、各連結成分が代表となる頂点を1つ持っています。
コンストラクタ
dsu d(n)
$n \ (0 \leq n \leq 10^8)$個の頂点で辺は$0$個の無向グラフを生成します。
(d というのは、無向グラフの名称です。)
計算量は、 $O(n)$ です。
merge
d.merge(a, b)
頂点$a$と頂点$b$ を辺$(a, b)$ で連結させます。$(0 \leq a,b < n)$
int型で、代表元を返します。
計算量は、ならし$O(\alpha (n))$ です。
same
d.same(a, b)
頂点$a,b$ が連結ならtrueを、そうでないならfalseを返します。$(0 \leqq a, b < n)$
計算量は、ならし$O(\alpha (n))$ です。
leader
d.leader(a)
頂点$a$を含む連結成分の代表元をint型で返します。 $(0 \leq a < n)$
計算量は、ならし$O(\alpha (n))$ です。
size
d.size(a)
頂点$a$を含む連結成分に、いくつ点が繋がっているかをint型で返します。$(0 \leq a < n)$
計算量は、ならし$O(\alpha (n))$ です。
groups
d.groups()
グラフを連結成分ごとに分け、その情報を vector<vector<int>> で返します。
計算量は、$O(n)$ です。
例えば、上のようなグラフでは、 0と1、2と3 が連結していて、連結成分は2つあります。
その場合、vector<vector<int>> で、{{0, 1}, {2, 3}} が返ってきます。
A - Disjoint Set Union
#include <bits/stdc++.h>
#include <atcoder/all> //読み込む
using namespace std;
using namespace atcoder;
//Created by karaju.
signed main(void){
int n, q;
cin >> n >> q;
dsu d(n);
//n頂点0辺の無向グラフを生成
for(int i = 0; i < q; i++){
int a, u, v;
cin >> a >> u >> v;
if(a == 0){
d.merge(u, v); //連結させる
}
else{
if(d.same(u, v)){ //もし連結なら
cout << 1 << endl;
}
else{
cout << 0 << endl;
}
}
}
}
Fenwick Tree
長さ$N$の配列に対して、
- 1つの要素を変更する
- 区間の要素の総和を求める
ことが$O(\log N)$ でできるデータ構造です。
コンストラクタ
fenwick_tree<int> fw(n)
長さ$n (0 \leq n \leq 10^8)$で初期値が$0$の配列を生成します。
計算量は、$O(n)$ です。
add
fw.add(p, x);
a[p] に $x$ を加えます。 $(0 \leq p < n)$
計算量は、$O(\log n)$ です。
sum
fw.sum(l, r)
a[l] から a[r - 1] までの総和を求めます。
計算量は、$O(\log n)$ です。
B - Fenwick Tree
#include <bits/stdc++.h>
#include <atcoder/all> //読み込む
using namespace std;
using namespace atcoder;
//Created by karaju.
signed main(void){
int n, q;
cin >> n >> q;
fenwick_tree<long long> fw(n); //配列作成
for(int i = 0; i < n; i++){
int a;
cin >> a;
fw.add(i, a); //数列を用意
}
for(int i = 0; i < q; i++){
int t;
cin >> t;
if(t == 0){
int p, x;
cin >> p >> x;
fw.add(p, x); //xを加える
}
else{
int l, r;
cin >> l >> r;
cout << fw.sum(l, r) << endl;
}
}
}
未完成ですが、記事の引用が必要となったので公開。