#844618 (Rust) No.789 範囲の合計

• 問題: No.789 範囲の合計
• ユーザー: sakikuroe
• 提出日時: 2023-02-28 18:35:39
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 310 ms / 1,000 ms
• コード長: 3,832 bytes
• コンパイル時間: 22,741 ms
• コンパイル使用メモリ: 379,004 KB
• 実行使用メモリ: 54,236 KB
• 最終ジャッジ日時: 2024-09-15 21:08:20
• 合計ジャッジ時間: 17,771 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
other	AC * 15

ソースコード

use std::collections::HashMap;

#[macro_export]
macro_rules! read_line {
    ($($xs: tt)*) => {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        expand!(iter, $($xs)*);
    };
}

#[macro_export]
macro_rules! expand {
    ($iter: expr,) => {};
    ($iter: expr, mut $var: ident : $type: tt, $($xs: tt)*) => {
        let mut $var = value!($iter, $type);
        expand!($iter, $($xs)*);
    };
    ($iter: expr, $var: ident : $type: tt, $($xs: tt)*) => {
        let $var = value!($iter, $type);
        expand!($iter, $($xs)*);
    };
}

#[macro_export]
macro_rules! value {
    ($iter:expr, ($($type: tt),*)) => {
        ($(value!($iter, $type)),*)
    };
    ($iter: expr, [$type: tt; $len: expr]) => {
        (0..$len).map(|_| value!($iter, $type)).collect::<Vec<_>>()
    };
    ($iter: expr, Chars) => {
        value!($iter, String).unwrap().chars().collect::<Vec<_>>()
    };
    ($iter: expr, $type: ty) => {
        if let Some(v) = $iter.next() {
            v.parse::<$type>().ok()
        } else {
            None
        }
    };
}


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

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
    }
}

/// Let $\\{a_{i}\\}_{i=1}^{N}$ be a sequence of type Monoid::S.
pub struct SegmentTreeDynamic<M>
where
    M: Monoid,
{
    size: usize,
    data: HashMap<usize, M::S>,
}

impl<M> SegmentTreeDynamic<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();
        SegmentTreeDynamic::<M> {
            size,
            data: HashMap::new(),
        }
    }

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

    /// Returns $a_{idx}$.
    pub fn get(&self, idx: usize) -> M::S {
        self.fold(idx, idx + 1)
    }

    /// 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 sum_l = M::id();
        let mut sum_r = M::id();

        while l < r {
            if l % 2 == 0 {
                sum_l = M::op(&sum_l, &self.data.get(&(l)).unwrap_or(&M::id()));
            }
            if r % 2 == 0 {
                sum_r = M::op(&self.data.get(&(r - 1)).unwrap_or(&M::id()), &sum_r);
            }
            l = l / 2;
            r = (r - 1) / 2;
        }

        M::op(&sum_l, &sum_r)
    }
}

fn main() {
    read_line!(n: usize,);
    let n = n.unwrap();

    let mut seg = SegmentTreeDynamic::<AddMonoid>::new(1000100010);
    let mut ans = 0;

    for _ in 0..n {
        read_line!(t: usize, x: usize, y: usize,);
        let t = t.unwrap();
        let x = x.unwrap();
        let y = y.unwrap();

        if t == 0 {
            let temp = seg.get(x);
            seg.update(x, temp + y);
        } else {
            let l = x;
            let r = y;
            ans += seg.fold(l, r + 1);
        }
    }

    println!("{}", ans);
}