Rust自分用メモ(随時更新)

fn main() {
  let n = 5_usize;
  let ans = (1..=n).product::<usize>();
  println!("{}", ans); // 120
}

fn main() {
    let s = [3,4,5];
    // 配列から2個取り出して掛け算をした結果の合計を求める
    println!(
        "{}",
        s.iter().combinations(2).fold(0, |acc, f| acc + f[0] * f[1])
    );
    // mapを使った場合
    println!("{}", s.iter().combinations(2).map(|f| f[0] * f[1]).sum::<usize>());
}

fn lower_bound<T: Ord>(a: &[T], x: T) -> usize {
    a.binary_search_by(|c| match c.cmp(&x) {
        std::cmp::Ordering::Equal => std::cmp::Ordering::Greater,
        ord => ord,
    })
    .unwrap_err()
}

fn upper_bound<T: Ord>(a: &[T], x: T) -> usize {
    a.binary_search_by(|c| match c.cmp(&x) {
        std::cmp::Ordering::Equal => std::cmp::Ordering::Less,
        ord => ord,
    })
    .unwrap_err()
}

/// セグメント木
/// 使い方
/// let mut segtree = SegmentTree::new(N, 0, |a, b| a ^ b);
/// segtree.update(i, x); データの更新(現在値と演算した結果が保持される)
/// segtree.replace(i, x); データの上書き更新(現在値を上書きする、演算なし)
/// segtree.query(l, r); 区間[l, r)の演算結果
struct SegmentTree<F, T> {
    size: usize,
    tree: Vec<T>,
    element: T,
    eval: F,
}

impl<F: Fn(T, T) -> T, T: Copy + Eq + std::fmt::Debug> SegmentTree<F, T> {
    /// セグメント木の構築
    /// 使い方
    /// let mut segtree = SegmentTree::new(size, element, |a, b| a ^ b);
    /// size: usize セグメント木のサイズ
    /// element: T セグメント木の初期値(Tの単位元)
    /// eval: F セグメント木の演算
    fn new(size: usize, element: T, eval: F) -> Self {
        let size = size.next_power_of_two();
        Self {
            size,
            tree: vec![element; 2 * size],
            element,
            eval,
        }
    }

    /// データ挿入
    /// 使い方 segtree.update(i, x);
    /// i:usize 挿入するインデックス(1-indexed)
    /// x:T 挿入する値
    /// 注意 挿入する値は現在値と演算した結果が保持される
    fn update(&mut self, i: usize, x: T) {
        let mut i = i + self.size - 1;
        self.tree[i] = (self.eval)(self.tree[i], x);
        while i > 1 {
            i /= 2;
            self.tree[i] = (self.eval)(self.tree[2 * i], self.tree[2 * i + 1]);
        }
    }

    /// データの上書き更新
    /// 使い方 segtree.replace(i, x);
    /// i:usize 更新するインデックス(1-indexed)
    /// x:T 更新する値
    /// 注意 更新する値は現在値を上書きする(演算なし)
    fn replace(&mut self, i: usize, x: T) {
        let mut i = i + self.size - 1;
        self.tree[i] = x;
        while i > 1 {
            i /= 2;
            self.tree[i] = (self.eval)(self.tree[2 * i], self.tree[2 * i + 1]);
        }
    }

    /// 区間演算
    /// 使い方 segtree.query(l, r);
    /// l:usize 区間の左端
    /// r:usize 区間の右端
    fn query(&self, l: usize, r: usize) -> T {
        let mut l = l + self.size - 1;
        let mut r = r + self.size - 1;
        let mut result = self.element;
        while l <= r {
            if l % 2 == 1 {
                result = (self.eval)(result, self.tree[l]);
                l += 1;
            }
            if r % 2 == 0 {
                result = (self.eval)(result, self.tree[r]);
                r -= 1;
            }
            l /= 2;
            r /= 2;
        }
        result
    }
}