Rustで競技プログラミングよくばりセット

競技プログラミングを行う上で使用頻度の高いアルゴリズムやデータ構造を、Rust（プログラミング言語）で実装するためのノートです。各アルゴリズムの実装と、それを用いる問題や解答例を掲載しています。

# 目次

## 関数/メソッド
- [最小値/最大値 (min/max)](#最小値最大値-minmax)
- [絶対値 (abs)](#絶対値-abs)
- [スワップ (swap)](#スワップ-swap)
- [ソート (sort)](#ソート-sort)
- [反転 (reverse)](#反転-reverse)
- [重複要素の削除 (unique, dedup)](#重複要素の削除-unique-dedup)

## データ構造
- [動的配列 (vector)](#動的配列-vector)
- [スタック (stack)](#スタック-stack)
- [キュー (queue)](#キュー-queue)
- [優先度付きキュー (priority queue)](#優先度付きキュー-priority-queue)
- [Set](#set)
- [Map](#map)
- [Union-Find木 (素集合データ構造)](#union-find木-素集合データ構造)
- [Mod Int (Mint, ModInt)](#mod-int-mint-modint)
- [Segment Tree (セグメント木)](#segment-tree-セグメント木)

## アルゴリズム
- [二分探索 (Binary search, lower bound, upper bound)](#二分探索-binary-search-lower-bound-upper-bound)
- [再帰](#再帰)
- [メモ化再帰](#メモ化再帰)

グラフ関連
- [幅優先探索 (BFS, breadth first search)](#幅優先探索-bfs-breadth-first-search)
- [ダイクストラ法 (Dijkstra's algorithm)](#ダイクストラ法-dijkstras-algorithm)
- [最小全域木 (クラスカル法, Kruskal's algorithm)](#最小全域木-クラスカル法-kruskals-algorithm)

整数論関連
- [最大公約数/最小公倍数 (GCD/LCM)](#最大公約数最小公倍数-gcdlcm)
- [素数判定](#素数判定)
- [約数列挙](#約数列挙)
- [素因数分解 (Integer factorization)](#素因数分解-integer-factorization)

# 関数/メソッド

## 最小値/最大値 (min/max)

- 最小値/最大値を取るための関数です。
- 標準の[std::cmp::{min, max}](https://doc.rust-lang.org/std/cmp/index.html)で実現できます。

```rust
use std::cmp;

fn main() {
    // min
    println!("{}", cmp::min(1, 2)); // 1
    println!("{}", cmp::min(1, -1)); // -1

    // max
    println!("{}", cmp::max(1, 2)); // 2
    println!("{}", cmp::max(1, -1)); // 1
}
```

__例__

1. AtCoder Beginner Contest 052 A - Two Rectangles【[問題](https://atcoder.jp/contests/abc052/tasks/abc052_a) / [解答例](https://atcoder.jp/contests/abc052/submissions/34842800)】
1. AtCoder Beginner Contest 098 A - Add Sub Mul【[問題](https://atcoder.jp/contests/abc098/tasks/abc098_a) / [解答例](https://atcoder.jp/contests/abc098/submissions/34842820)】

## 絶対値 (abs)

- 絶対値を取るためのメソッドです。
- 標準の[abs()](https://doc.rust-lang.org/std/primitive.isize.html#method.abs)で使えます。

```rust
fn main (){
    println!("{}", (-1isize).abs()); // 1
    println!("{}", (1isize).abs()); // 1
    println!("{}", (-100isize).abs()); // 100

    // !注意! 次の例では-100になる。 (∵ -100isize.abs() -> -(100isize.abs()) -> -100 のように解釈されるため)
    println!("{}", -100isize.abs()); // -100
}
```

__例__

1. AtCoder Beginner Contest 188 A - Three-Point Shot【[問題](https://atcoder.jp/contests/abc188/tasks/abc188_a) / [解答例](https://atcoder.jp/contests/abc188/submissions/34842837)】

## スワップ (swap)
- ２つの値をスワップする関数です。
- 標準の[std::mem::swap()](https://doc.rust-lang.org/stable/std/mem/fn.swap.html)でできます。

```rust
use std::mem;

fn main (){
    let mut a = 1;
    let mut b = 2;
    println!("a: {}, b: {}", a, b); // a: 1, b: 2
    mem::swap(&mut a, &mut b);
    println!("a: {}, b: {}", a, b); // a: 2, b: 1
}
```

__例__

1. AtCoder Beginner Contest 161 A - ABC Swap【[問題](https://atcoder.jp/contests/abc161/tasks/abc161_a) / [解答例](https://atcoder.jp/contests/abc161/submissions/34842850)】

## ソート (sort)
### sort()
- Vectorの要素を特定の順番で並び替えるためのメソッドです。
- 標準の[sort()](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort)で昇順に並び替えることができます。

```rust
fn main() {
    let mut v = vec![3, 1, 4, 1, 5, 9, 2];
    v.sort();
    println!("{:?}", v); // [1, 1, 2, 3, 4, 5, 9]
}
```

__例__

1. Chokudai SpeedRun 001　D - ソート【[問題](https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_d) / [解答例](https://atcoder.jp/contests/chokudai_S001/submissions/34842857)】

### sort_by()
- [sort_by()](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_by)では、比較関数をもとにして並び替えることができます。
- 例えば、[cmp()](https://doc.rust-lang.org/std/cmp/trait.Ord.html#tymethod.cmp)が出力する順序関係を逆転させることで、降順に並び替えることができます。

```rust
fn main() {
    let mut v = vec![3, 1, 4, 1, 5, 9, 2];
    v.sort_by(|a, b| a.cmp(b).reverse());
    println!("{:?}", v); // [9, 5, 4, 3, 2, 1, 1]
}
```

__例__

1. AtCoder Beginner Contest 260 B - Better Students Are Needed!【[問題](https://atcoder.jp/contests/abc260/tasks/abc260_b) / [解答例](https://atcoder.jp/contests/abc260/submissions/34842890)】

また、[sort_by()](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_by)と[partial_cmp()](https://doc.rust-lang.org/std/cmp/trait.PartialOrd.html#tymethod.partial_cmp)組み合わせることによって、[Ord](https://doc.rust-lang.org/std/cmp/trait.Ord.html)トレイトが実装されていないf64型の[Vec](https://doc.rust-lang.org/std/vec/struct.Vec.html)をソートすることもできます。(Rustの小数には[Ord](https://doc.rust-lang.org/std/cmp/trait.Ord.html)トレイトが実装されていないため、sort()はできません。)

```rust
fn main() {
    let mut v = vec![3.0, 1.0, 4.0, 1.0, 5.0];
    v.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", v); // [1.0, 1.0, 3.0, 4.0, 5.0]
}
```

__例__

1. AtCoder Beginner Contest 138  C - Alchemist【[問題](https://atcoder.jp/contests/abc138/tasks/abc138_c) / [解答例](https://atcoder.jp/contests/abc138/submissions/34422238)】

### sort_by_key()
- [sort_by_key()](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_by_key)では、比較関数をもとにして並び替えることができます。
- 例えば、次のようにVectorをtupleのi番目の要素をもとにして並び替えることができます。

```rust
fn main() {
    let mut v = vec![(3, 1, 4), (1, 5, 9), (2, 6, 5)];
    // 各tupleの0番目の要素をもとにソート
    v.sort_by_key(|x| x.0);
    println!("{:?}", v); // [(_1_, 5, 9), (_2_, 6, 5), (_3_, 1, 4)]

    // 各tupleの1番目の要素をもとにソート
    v.sort_by_key(|x| x.1);
    println!("{:?}", v); // [(3, _1_, 4), (1, _5_, 9), (2, _6_, 5)]

    // 各tupleの2番目の要素をもとにソート
    v.sort_by_key(|x| x.2);
    println!("{:?}", v); // [(3, 1, _4_), (2, 6, _5_), (1, 5, _9_)]
}
```

## 反転 (reverse)

- Vectorの要素を反転させるためのメソッドです。
- 標準のrevese()で反転させることができます。

```rust
fn main() {
    let mut v = vec![3, 1, 4, 1, 5, 9, 2];
    v.reverse();
    println!("{:?}", v); // [2, 9, 5, 1, 4, 1, 3]
}
```

## 重複要素の削除 (unique, dedup)
- 連続した要素を削除するためのメソッドです。
- 標準の[dedup()](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.dedup)で行うことができます。

```rust
fn main() {
    let mut v = vec![1, 1, 2, 3, 4, 5, 5];
    v.dedup();
    println!("{:?}", v); // [1, 2, 3, 4, 5]

    let mut u = vec![1, 1, 1, 2, 2, 1, 1, 1, 0, 3, 3];
    u.dedup();
    println!("{:?}", u); // [1, 2, 1, 0, 3]
}
```

# データ構造

## 動的配列 (vector)
標準の[std::vec](https://doc.rust-lang.org/std/vec/index.html)で実現できます。

```rust
fn main() {
    let mut v = vec![0, 1, 2, 3, 4];
    println!("{}", v.len()); // 5
    println!("{:?}", v); // [0, 1, 2, 3, 4]

    v[2] =  5;
    println!("{:?}", v); // [0, 1, 5, 3, 4]
}
```
## スタック (stack)
上で述べた[std::vec](https://doc.rust-lang.org/std/vec/index.html)のpush()とpop()を使うと実現できます。
```rust
fn main() {
    let mut stack = vec![];

    stack.push(0);
    stack.push(1);
    stack.push(2);
    println!("{:?}", stack); // [0, 1, 2]

    println!("{:?}", stack.pop()); // Some(2)

    println!("{:?}", stack); // [0, 1]
}
```

## キュー (queue)

標準の[std::collections::VecDeque](https://doc.rust-lang.org/std/collections/struct.VecDeque.html)で実現できます。
```rust
use std::collections::VecDeque;

fn main() {
    let mut que = VecDeque::new();

    que.push_back(0);
    que.push_back(1);
    que.push_back(2);
    println!("{:?}", que); // [0, 1, 2]

    println!("{:?}", que.pop_front()); // Some(0)
    println!("{:?}", que); // [1, 2]

    println!("{:?}", que.pop_front()); // Some(1)
    println!("{:?}", que); // [2]

    println!("{:?}", que.pop_front()); // Some(2)
    println!("{:?}", que); // []

    println!("{:?}", que.pop_front()); // None
}
```

## 優先度付きキュー (priority queue)

- 標準の[std::collections::BinaryHeap](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html)で実現できます。
- 要素が大きい順に取り出される点に注意してください。

```rust
use std::collections::BinaryHeap;

fn main() {
    let mut que = BinaryHeap::new();

    que.push(0);
    que.push(2);
    que.push(1);

    println!("{:?}", que.pop()); // Some(2)
    println!("{:?}", que.pop()); // Some(1)
    que.push(3);
    println!("{:?}", que.pop()); // Some(3)
    println!("{:?}", que.pop()); // Some(0)
    println!("{:?}", que.pop()); // None
}
```

__例__
1. AtCoder Beginner Contest 137 D - Summer Vacation【[問題](https://atcoder.jp/contests/abc137/tasks/abc137_d) / [解答例](https://atcoder.jp/contests/abc137/submissions/34842947)】

## Set

標準の[std::collections::HashSet](https://doc.rust-lang.org/std/collections/hash_set/struct.HashSet.html)で実現できます。

```rust
use std::collections::HashSet;

fn main() {
    let mut set = HashSet::new();

    set.insert(0);
    set.insert(1);
    set.insert(2);

    println!("{}", set.contains(&0)); // true
    println!("{}", set.contains(&3)); // false

    set.remove(&0);
    println!("{}", set.contains(&0)); // false
}
```

__例__
1. ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248) A - Lacked Number【[問題](https://atcoder.jp/contests/abc248/tasks/abc248_a) / [解答例](https://atcoder.jp/contests/abc248/submissions/34842997)】

## Map

標準の[std::collections::HashMap](https://doc.rust-lang.org/std/collections/hash_map/struct.HashMap.html)で実現できます。

```rust
use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();

    map.insert("zero", 0);
    map.insert("one", 1);
    map.insert("two", 2);

    println!("{:?}", map.get("zero")); // Some(0)
    println!("{:?}", map.get("three")); // None
}
```

## Union-Find木 (素集合データ構造)

- rankの大きさをもとにして併合(union)を行います。
- 標準のenumである[Ordering](https://doc.rust-lang.org/std/cmp/enum.Ordering.html)で順序を扱えます。

```rust
use std::cmp::Ordering;
 
#[derive(Clone)]
pub struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        UnionFind {
            parent: (0..n).collect::<Vec<_>>(),
            rank: vec![0; n],
        }
    }

    pub fn is_root(&self, x: usize) -> bool {
        self.parent[x] == x
    }

    pub fn find(&mut self, x: usize) -> usize {
        if self.is_root(x) {
            x
        } else {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
            root
        }
    }

    pub fn union(&mut self, x: usize, y: usize) {
        let (root_x, root_y) = (self.find(x), self.find(y));

        if root_x != root_y {
            match self.rank[root_x].cmp(&self.rank[root_y]) {
                Ordering::Less => {
                    self.parent[root_x] = root_y;
                }
                Ordering::Equal => {
                    self.parent[root_y] = root_x;
                    self.rank[root_x] += 1;
                }
                Ordering::Greater => {
                    self.parent[root_y] = root_x;
                }
            }
        }
    }

    pub fn is_same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}
```

__例__
1. AtCoder Typical Contest 001 B - Union Find【[問題](https://atcoder.jp/contests/atc001/tasks/unionfind_a) / [解答例](https://atcoder.jp/contests/atc001/submissions/34843026)】

- ある要素が属しているグループに含まれるノードの数を調べることができるように拡張すると、次のようになります。(get_sizeメソッドを追加しています)

```rust
use std::cmp::Ordering;

#[derive(Clone)]
pub struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
    size: Vec<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        UnionFind { parent: (0..n).collect::<Vec<_>>(), rank: vec![0; n], size: vec![1; n] }
    }

    pub fn is_root(&self, x: usize) -> bool {
        self.parent[x] == x
    }

    pub fn find(&mut self, x: usize) -> usize {
        if self.is_root(x) {
            x
        } else {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
            root
        }
    }

    pub fn union(&mut self, x: usize, y: usize) {
        let (root_x, root_y) = (self.find(x), self.find(y));

        if root_x != root_y {
            match self.rank[root_x].cmp(&self.rank[root_y]) {
                Ordering::Less => {
                    self.parent[root_x] = root_y;
                    self.size[root_y] += self.size[root_x];
                }
                Ordering::Equal => {
                    self.parent[root_y] = root_x;
                    self.size[root_x] += self.size[root_y];
                    self.rank[root_x] += 1;
                }
                Ordering::Greater => {
                    self.parent[root_y] = root_x;
                    self.size[root_x] += self.size[root_y];
                }
            }
        }
    }

    pub fn is_same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }

    pub fn get_size(&mut self, x: usize) -> usize {
        if self.is_root(x) {
            self.size[x]
        } else {
            let root = self.find(x);
            self.size[root]
        }
    }
}
```

__例__

1. AtCoder Beginner Contest 120 D - Decayed Bridges【[問題](https://atcoder.jp/contests/abc120/tasks/abc120_d) / [解答例](https://atcoder.jp/contests/abc120/submissions/34843059)】
1. AtCoder Regular Contest 107 C - Shuffle Permutation【[問題](https://atcoder.jp/contests/arc107/tasks/arc107_c) / [解答例](https://atcoder.jp/contests/arc107/submissions/35059554)】

## Mod Int (Mint, ModInt)

- [演算子オーバーロード](https://doc.rust-jp.rs/book-ja/ch19-03-advanced-traits.html)を用いると、四則演算が自然に行えるようになります。
- 四則演算の他には、inverse(逆元), pow(冪乗の計算, $a^{n}$), conbinarion(組み合わせ, $nCr$), permutation(順列, $nPr$), factorial(階乗, $n!$)などを実装しています。

```rust
use std::ops;

const MOD: usize = 1000000007;

#[derive(Copy, Clone)]
pub struct ModInt {
    value: usize,
}

impl ModInt {
    pub fn new(value: usize) -> ModInt {
        ModInt { value: value % MOD }
    }

    pub fn value(&self) -> usize {
        self.value
    }

    pub fn inverse(&self) -> ModInt {
        // (a, b) -> (x, y) s.t. a * x + b * y = gcd(a, b)
        fn extended_gcd(a: isize, b: isize) -> (isize, isize) {
            if (a, b) == (1, 0) {
                (1, 0)
            } else {
                let (x, y) = extended_gcd(b, a % b);
                (y, x - (a / b) * y)
            }
        }

        let (x, _y) = extended_gcd(self.value() as isize, MOD as isize);
        ModInt::new((MOD as isize + x) as usize)
    }

    // a^n
    pub fn pow(&self, mut n: usize) -> ModInt {
        let mut res = ModInt::new(1);
        let mut x = *self;
        while n > 0 {
            if n % 2 == 1 {
                res *= x;
            }
            x *= x;
            n /= 2;
        }
    
        res
    }
}

impl ops::Add for ModInt {
    type Output = ModInt;
    fn add(self, other: Self) -> Self {
        ModInt::new(self.value + other.value)
    }
}

impl ops::Sub for ModInt {
    type Output = ModInt;
    fn sub(self, other: Self) -> Self {
        ModInt::new(MOD + self.value - other.value)
    }
}

impl ops::Mul for ModInt {
    type Output = ModInt;
    fn mul(self, other: Self) -> Self {
        ModInt::new(self.value * other.value)
    }
}

impl ops::Div for ModInt {
    type Output = ModInt;
    fn div(self, other: Self) -> Self {
        self * other.inverse()
    }
}

impl ops::AddAssign for ModInt {
    fn add_assign(&mut self, other: Self) {
        *self = *self + other;
    }
}

impl ops::SubAssign for ModInt {
    fn sub_assign(&mut self, other: Self) {
        *self = *self - other;
    }
}

impl ops::MulAssign for ModInt {
    fn mul_assign(&mut self, other: Self) {
        *self = *self * other;
    }
}

impl ops::DivAssign for ModInt {
    fn div_assign(&mut self, other: Self) {
        *self = *self / other;
    }
}

// n!
pub fn factorial(n: usize) -> ModInt {
    (1..=n).fold(ModInt::new(1), |x, y| x * ModInt::new(y))
}

// nPr (https://ja.wikipedia.org/wiki/%E9%A0%86%E5%88%97#%E9%A0%86%E5%88%97%E3%81%AE%E6%95%B0%E3%81%88%E4%B8%8A%E3%81%92)
pub fn permutation(n: usize, r: usize) -> ModInt {
    if n < r {
        ModInt::new(0)
    } else {
        (n - r + 1..=n).fold(ModInt::new(1), |x, y| x * ModInt::new(y))
    }
}

// nCr (https://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B_(%E6%95%B0%E5%AD%A6))
pub fn combination(n: usize, r: usize) -> ModInt {
    if n < r {
        ModInt::new(0)
    } else {
        permutation(n, r) / factorial(r)
    }
}

// nHr (https://ja.wikipedia.org/wiki/%E9%87%8D%E8%A4%87%E7%B5%84%E5%90%88%E3%81%9B#%E9%87%8D%E8%A4%87%E7%B5%84%E5%90%88%E3%81%9B%E3%81%AE%E7%B7%8F%E6%95%B0)
pub fn homogeneous(n: usize, r: usize) -> ModInt {
    combination(n + r - 1, r)
}
```

```rust
fn main() {
    let mut a = ModInt::new(1000000000);
    a += ModInt::new(9);
    println!("{}", a.value()); // 2
  
    println!("{}", ModInt::new(2).inverse().value()); // 500000004
    println!("{}", ModInt::new(3).inverse().value()); // 333333336
}
```

__例__
1. AtCoder Beginner Contest 034 C - 経路【[問題](https://atcoder.jp/contests/abc034/tasks/abc034_c) / [解答例](https://atcoder.jp/contests/abc034/submissions/34843124)】
1. AtCoder Regular Contest 145 C - Split and Maximize 【[問題](https://atcoder.jp/contests/arc145/tasks/arc145_c) / [解答例](https://atcoder.jp/contests/arc145/submissions/34843164)】

## Segment Tree (セグメント木)
- RustではACL(AtCoder Library)が使えないので各自で実装をします。
- 非再帰型の実装です。
![Q5aMu1Td.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2611053/91594c06-54ae-4ff3-8882-0ebe2440f0bc.jpeg)

- モノイド$(S, \bullet(op), id)(S:$ 集合、$\bullet: S$上の二項演算、$id: S$の$\bullet$に関する単位元$)$を用いて、数列$\lbrace a_i \rbrace_{i=1}^n$に対して、次の1~3ができます。
    1. update: $a_{i}$ をxに更新
    1. get: $a_{i}$ の取得
    1. fold: ($a_{l} \bullet a_{l+1} \bullet \cdots \bullet a_{r - 1}$) の取得(半開区間$[l, r)$)
- [next_power_of_two](https://doc.rust-lang.org/std/primitive.usize.html#method.next_power_of_two)を用いると、セグメント木のノードの数を簡単に決定できます。
- 具体的な使い方は例の問題を見てください。

```rust
pub trait Monoid {
    type S;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    fn id() -> Self::S;
}

pub struct SegmentTree<M>
where
    M: Monoid,
{
    size: usize,
    data: Vec<M::S>,
}

impl<M> SegmentTree<M>
where
    M: Monoid,
    M::S: Clone,
{
    /// Creates a segment tree with $\\{a_{i}\\}_{i=1}^{N}$ inside.
    /// n: lenght of $\\{a_{i}\\}_{i=1}^{N}$ (i.e. N)
    pub fn new(n: usize) -> Self {
        let size = n.next_power_of_two();
        SegmentTree::<M> { size, data: vec![M::id(); 2 * size - 1] }
    }

    /// Returns lenght of $\\{a_{i}\\}_{i=1}^{N}$ (i.e. Return N)
    pub fn len(&self) -> usize {
        self.size
    }

    /// Sets x to $a_{idx}$.
    pub fn set(&mut self, mut idx: usize, x: M::S) {
        idx += self.size - 1;
        self.data[idx] = x;
    }

    /// Builds segment tree.
    pub fn build(&mut self) {
        for idx in (0..self.size - 1).rev() {
            self.data[idx] = M::op(&self.data[2 * idx + 1], &self.data[2 * idx + 2]);
        }
    }

    /// Updates $a_{idx}$ to x.
    pub fn update(&mut self, mut idx: usize, x: M::S) {
        idx += self.size - 1;
        self.data[idx] = x;
        while idx > 0 {
            idx = (idx - 1) / 2;
            self.data[idx] = M::op(&self.data[2 * idx + 1], &self.data[2 * idx + 2]);
        }
    }

    /// Returns $a_{idx}$.
    pub fn get(&self, mut idx: usize) -> M::S {
        idx += self.size - 1;
        self.data[idx].clone()
    }

    /// Returns the result (fold op $\left[a_{l}, ... ,a_{r}\right)).$
    /// (i.e. Return $a_{l} (op) a_{l + 1} (op) \cdots (op) a_{r-1})$
    /// Notice that this is a half-opened section.
    pub fn fold(&self, mut l: usize, mut r: usize) -> M::S {
        l += self.size - 1;
        r += self.size - 1;

        let mut xl = M::id();
        let mut xr = M::id();

        while l < r {
            if l % 2 == 0 {
                xl = M::op(&xl, &self.data[l]);
            }
            if r % 2 == 0 {
                xr = M::op(&self.data[r - 1], &xr);
            }
            l = l / 2;
            r = (r - 1) / 2;
        }

        M::op(&xl, &xr)
    }
}
```

モノイド$(S, \bullet(op), id)$は次の様に定義できます。  

```rust
pub struct MinMonoid;

impl Monoid for MinMonoid {
    type S = usize;
    fn op(a: &Self::S, b: &Self::S) -> Self::S {
        std::cmp::min(*a, *b)
    }
    fn id() -> Self::S {
        std::usize::MAX
    }
}

pub struct MaxMonoid;

impl Monoid for MaxMonoid {
    type S = usize;
    fn op(a: &Self::S, b: &Self::S) -> Self::S {
        std::cmp::max(*a, *b)
    }
    fn id() -> Self::S {
        0
    }
}

pub struct AddMonoid;

impl Monoid for AddMonoid {
    type S = usize;
    fn op(a: &Self::S, b: &Self::S) -> Self::S {
        *a + *b
    }
    fn id() -> Self::S {
        0
    }
}

pub struct MulMonoid;

impl Monoid for MulMonoid {
    type S = usize;
    fn op(a: &Self::S, b: &Self::S) -> Self::S {
        *a * *b
    }
    fn id() -> Self::S {
        1
    }
}
```

__例__

1. AOJ DSL_2_A Range Min Query (RMQ)【[問題](https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A) / [解答例](https://onlinejudge.u-aizu.ac.jp/status/users/Kurosaki96/submissions/1/DSL_2_A/judge/6507096/Rust)】
1. AOJ DSL_2_B Range Sum Query (RSQ)【[問題](https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B) / [解答例](https://onlinejudge.u-aizu.ac.jp/status/users/Kurosaki96/submissions/1/DSL_2_B/judge/6507097/Rust)】
1. AOJ DSL_2_E Range Add Query【[問題](https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_E) / [解答例](https://onlinejudge.u-aizu.ac.jp/status/users/Kurosaki96/submissions/1/DSL_2_E/judge/6507098/Rust)】
1. AtCoder Beginner Contest 125 C - GCD on Blackboard 【[問題](https://atcoder.jp/contests/abc125/tasks/abc125_c) / [解答例](https://atcoder.jp/contests/abc125/submissions/34843252)】(+ 最大公約数)

# アルゴリズム

## 二分探索 (Binary search, lower bound, upper bound)

- めぐる式二分探索法によってlower bound / upper boundを実装すると次の様になります。
- 配列の要素にOrd triatが実装されている必要があります。
- isize型とusize型の間で足し算などの計算をする場合、適当に変換する必要があります。

```rust
pub trait BinarySearch<T> {
    fn lower_bound(&self, key: T) -> usize;
    fn upper_bound(&self, key: T) -> usize;
}

impl<T> BinarySearch<T> for [T]
where
    T: Ord,
{
    fn lower_bound(&self, key: T) -> usize {
        let mut ng = -1 as isize;
        let mut ok = self.len() as isize;
        while ok - ng > 1 {
            let mid = (ok + ng) / 2;
            if key <= self[mid as usize] {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        ok as usize
    }

    fn upper_bound(&self, key: T) -> usize {
        let mut ng = -1 as isize;
        let mut ok = self.len() as isize;
        while ok - ng > 1 {
            let mid = (ok + ng) / 2;
            if key < self[mid as usize] {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        ok as usize
    }
}
```

__例__
1. AtCoder Beginner Contest 077 C - Snuke Festival【[問題](https://atcoder.jp/contests/abc077/tasks/arc084_a) / [解答例](https://atcoder.jp/contests/abc077/submissions/34843278)】

__例__ (lower bound / upper bound以外)
1. 競プロ典型 90 問 001 - Yokan Party（★4）【[問題](https://atcoder.jp/contests/typical90/tasks/typical90_a) / [解答例](https://atcoder.jp/contests/typical90/submissions/34778456)】



## 再帰

- フィボナッチ数を求めるサンプルです

```rust
fn fib(n: usize) -> usize {
    match n {
        0 => 0,
        1 => 1,
        _ => fib(n - 2) + fib(n - 1)
    }
}

fn main(){
    println!("{}", fib(10)); // 55
}
```
__例__
1. AtCoder Beginner Contest 247 C - 1 2 1 3 1 2 1【[問題](https://atcoder.jp/contests/abc247/tasks/abc247_c) / [解答例](https://atcoder.jp/contests/abc247/submissions/34843349)】

## メモ化再帰

- フィボナッチ数を求めるサンプルです。
- Rustでは気軽にグローバル変数を扱えないので、メモをMapやVectorで持ち、必要に応じて再利用するようにすると実装できます。

```rust
use std::collections::HashMap;

fn fib(n: usize, memo: &mut HashMap<usize, u128>) -> u128 {
    if let Some(value) = memo.get(&n) {
        return *value;
    }

    let res = match n {
        0 => 0,
        1 => 1,
        _ => fib(n - 2, memo) + fib(n - 1, memo)
    };

    memo.insert(n, res);
    res
}

fn main(){
    let mut memo = HashMap::new();
    println!("{}", fib(100, &mut memo)); // 354224848179261915075
}
```

1. AtCoder Beginner Contest 275 D - Yet Another Recursive Function 【[問題](https://atcoder.jp/contests/abc275/tasks/abc275_d) / [解答例](https://atcoder.jp/contests/abc275/submissions/36109774)】

## 幅優先探索 (BFS, breadth first search)

- データ構造の章で述べたように、先入れ先出し(FIFO)のQueueは[std::collections::VecDeque](https://doc.rust-lang.org/std/collections/struct.VecDeque.html)で実現できます。
- 『AtCoder Beginner Contest 007 C - 幅優先探索』の解法サンプルです。
- while letを使うと実装が楽になります。

```rust
use proconio::{
    input,
    marker::{Chars, Usize1},
};
use std::collections::VecDeque;

fn main() {
    input! {
        h: usize, w: usize,
        sy: Usize1, sx: Usize1,
        gy: Usize1, gx: Usize1,
        c: [Chars; h],
    }

    let mut que = VecDeque::new();
    que.push_back((sy, sx));
    let mut dist: Vec<Vec<Option<usize>>> = vec![vec![None; w]; h];
    dist[sy][sx] = Some(0);

    while let Some((y, x)) = que.pop_front() {
        if (y, x) == (gy, gx) {
            println!("{}", dist[y][x].unwrap());
            return;
        }

        let dy = vec![1, 0, -1, 0];
        let dx = vec![0, 1, 0, -1];

        for i in 0..4 {
            let dy = dy[i];
            let dx = dx[i];

            let next_y = y as isize + dy;
            let next_x = x as isize + dx;

            if 0 <= next_y
                && next_y < h as isize
                && 0 <= next_x
                && next_x < w as isize
                && dist[next_y as usize][next_x as usize].is_none()
                && c[next_y as usize][next_x as usize] == '.'
            {
                que.push_back((next_y as usize, next_x as usize));
                dist[next_y as usize][next_x as usize] = Some(dist[y][x].unwrap() + 1);
            }
        }
    }
}
```

__例__
1. AtCoder Beginner Contest 007 C - 幅優先探索 【[問題](https://atcoder.jp/contests/abc007/tasks/abc007_3) / [解答例](https://atcoder.jp/contests/abc007/submissions/34843450)】
1. AtCoder Beginner Contest 272 D - Root M Leaper 【[問題](https://atcoder.jp/contests/abc272/tasks/abc272_d) / [解答例](https://atcoder.jp/contests/abc272/submissions/35517706)】

## ダイクストラ法 (Dijkstra's algorithm)

- 次の様に実装できます。
- 『AOJ 単一始点最短経路』の解法サンプルです。
- 上で述べた様に、優先度付きキューは[std::collections::BinaryHeap](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html)で実装できます。
    - RustのBinaryHeapでは、標準で大きい順に要素が取り出されます。
    - State構造体を実装し、適切に順序関係(Ord, PartialEq)を入れることによって、小さい順に取り出せるようにします。

```rust
use std::{cmp::Ordering, collections::BinaryHeap};

const INF: usize = std::usize::MAX;

#[derive(Clone, PartialEq, Eq)]
pub struct State<T> {
    pub id: usize,
    pub priority: T,
}

impl<T> Ord for State<T>
where
    T: Ord,
{
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority.cmp(&other.priority).reverse()
    }
}

impl<T> PartialOrd for State<T>
where
    T: Ord,
{
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

#[derive(Clone, PartialEq, Eq)]
pub struct Edge<T> {
    pub src: usize,
    pub dst: usize,
    pub weight: T,
}

#[derive(Clone)]
pub struct Graph<T> {
    pub edges: Vec<Vec<Edge<T>>>,
}

impl<T> Graph<T>
where
    T: Clone,
{
    pub fn new(n: usize) -> Self {
        Graph {
            edges: vec![vec![]; n],
        }
    }

    pub fn len(&self) -> usize {
        self.edges.len()
    }

    pub fn add_edge(&mut self, src: usize, dst: usize, weight: T) {
        self.edges[src].push(Edge { src, dst, weight });
    }
}

fn main() {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    let word_list: Vec<&str> = line.split_whitespace().collect();
    let v_size: usize = word_list[0].parse::<usize>().unwrap();
    let e_size: usize = word_list[1].parse::<usize>().unwrap();
    let r: usize = word_list[2].parse::<usize>().unwrap();

    let mut std: Vec<(usize, usize, usize)> = Vec::new();
    for _ in 0..e_size {
        line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let word_list: Vec<usize> = {
            let word_list: Vec<&str> = line.split_whitespace().collect();
            word_list.into_iter().map(|s| s.parse::<usize>().unwrap()).collect()
        };
        std.push((word_list[0], word_list[1], word_list[2]));
    }

    let mut g = Graph::new(v_size);
    for &(u, v, c) in std.iter() {
        g.add_edge(u, v, c);
    }

    let mut dist = vec![INF; g.len()];
    dist[r] = 0;

    let mut que = BinaryHeap::new();
    que.push(State { id: r, priority: 0 });

    while let Some(State { id, priority }) = que.pop() {
        if priority > dist[id] {
            continue;
        }
        for e in &g.edges[id] {
            if dist[e.dst] > (dist[e.src]).checked_add(e.weight).unwrap_or(INF) {
                dist[e.dst] = dist[e.src] + e.weight;
                que.push(State {
                    id: e.dst,
                    priority: dist[e.dst],
                });
            }
        }
    }

    for i in 0..v_size {
        let ans = dist[i];
        if ans < INF {
            println!("{}", ans);
        } else {
            println!("INF");
        }
    }
}
```

__例__
1. AOJ 単一始点最短経路【[問題](https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A) / [解答例](https://onlinejudge.u-aizu.ac.jp/status/users/Kurosaki96/submissions/1/GRL_1_A/judge/6962879/Rust)】

## 最小全域木 (クラスカル法, Kruskal's algorithm)

- [Union-Find](#union-find木-素集合データ構造)を用いて閉路の判定を行います。
- 最小全域木の一つを構成する辺のVectorを返す実装です。
- [flatten()](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.flatten)を使うと実装が楽です。

```rust
impl<T> Graph<T>
where
    T: Clone + Copy + Ord,
{
    pub fn kruskal(&self) -> Vec<Edge<T>> {
        let mut res = vec![];
        let mut uf = UnionFind::new(self.len());

        let mut all_edges = self
            .edges
            .iter()
            .cloned()
            .flatten()
            .collect::<Vec<Edge<T>>>();

        all_edges.sort_by_key(|e| e.weight);

        for e in all_edges {
            if !uf.is_same(e.src, e.dst) {
                uf.union(e.src, e.dst);
                res.push(e);
            }
        }

        res
    }
}
```

__例__
1. AOJ GRL_2_A 最小全域木【[問題](https://onlinejudge.u-aizu.ac.jp/problems/GRL_2_A) / [解答例](https://onlinejudge.u-aizu.ac.jp/status/users/Kurosaki96/submissions/1/GRL_2_A/judge/6964918/Rust)】



## 最大公約数/最小公倍数 (GCD/LCM)

- ユークリッドの互除法を実装します。
- 上で述べた[std::mem::swap](https://doc.rust-lang.org/stable/std/mem/fn.swap.html)関数を用いるとswapができます。

```rust
use std::mem;

pub fn gcd(mut a: usize, mut b: usize) -> usize {
    if a < b {
        mem::swap(&mut a, &mut b);
    }
    while b != 0 {
        let temp = a % b;
        a = b;
        b = temp;
    }
    a
}
/*
Rust 1.59.0からは分割代入(destructuring assignment)ができるようになったため
pub fn gcd(mut a: usize, mut b: usize) -> usize {
    if a < b {
        (a, b) = (b, a);
    }
    while b != 0 {
        (a, b) = (b, a % b);
    }
    a
}
の様にtempを挟まなくても動きます。swapも簡潔に書けます。各種コンテストサイトの言語アップデートが楽しみです。(2022/9)
*/

pub fn lcm(a: usize, b: usize) -> usize {
    a * b / gcd(a, b)
}
```

- gcd()は、再帰を用いることによって、次のように書くこともできます

```rust
pub fn gcd(a: usize, b: usize) -> usize {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}
```

## 素数判定
- $N$ に対して $\sqrt{N}$までの数が約数かどうか判定するアルゴリズムです。
- [take_while](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.take_while)を使うことで簡単に約数の候補を絞れます。

```rust
pub fn is_prime(n: usize) -> bool {
    if n == 0 || n == 1 {
        return false;
    }

    for i in (2..).take_while(|&x| x * x <= n) {
        if n % i == 0 {
            return false;
        }
    }

    true
}
```
__例__
1. AtCoder Beginner Contest 084 D - 2017-like Number【[問題](https://atcoder.jp/contests/abc084/tasks/abc084_d) / [解答例](https://atcoder.jp/contests/abc084/submissions/34843597)】

## 約数列挙

- $\sqrt{N}$まで判定するアルゴリズムです。
- 素数判定と同様に[take_while](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.take_while)が便利です。

```rust
pub fn gen_divisors(n: usize) -> Vec<usize> {
    let mut res = vec![];

    for i in (1..).take_while(|&x| x * x <= n) {
        if n % i == 0 {
            if i * i == n {
                res.push(i);
            } else {
                res.push(i);
                res.push(n / i);
            }
        }
    }
    res.sort();

    res
}

fn main() {
    println!("{:?}", gen_divisors(36)); // [1, 2, 3, 4, 6, 9, 12, 18, 36]
}
```

__例__
1. AtCoder Beginner Contest 180 C - Cream puff【[問題](https://atcoder.jp/contests/abc180/tasks/abc180_c) / [解答例](https://atcoder.jp/contests/abc180/submissions/34843606)】

## 素因数分解 (Integer factorization)

- $n \in \mathbb{N},n = p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{k}^{e_{k}}$と分解されるとき、$[(p_{1}: e_{1}), (p_{2}: e_{2}), \dots , (p_{k}: e_{k})]$なるmapを返す実装です。
- mapのentryを使うと指数を簡単に記録できます。
- [BTreeMap](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html)で実装していますが、[HashMap](https://doc.rust-lang.org/stable/std/collections/struct.HashMap.html)でも問題無いです。

```rust
use std::collections::BTreeMap;

pub fn integer_factorization(mut n: usize) -> BTreeMap<usize, usize> {
    let mut map = BTreeMap::new();

    let mut i = 2;
    while i * i <= n {
        while n % i == 0 {
            *map.entry(i).or_insert(0) += 1;
            n /= i;
        }
        i += 1;
    }

    if n != 0 && n != 1 {
        *map.entry(n).or_insert(0) += 1;
    }

    map
}
```

```rust
fn main() {
    println!("{:?}", integer_factorization(12)); // {2: 2, 3: 1}
    println!("{:?}", integer_factorization(100)); // {2: 2, 5: 2}
}
```