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

• 問題: No.789 範囲の合計
• ユーザー: niuez
• 提出日時: 2019-07-25 10:38:52
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 186 ms / 1,000 ms
• コード長: 3,686 bytes
• コンパイル時間: 13,457 ms
• コンパイル使用メモリ: 377,964 KB
• 実行使用メモリ: 34,688 KB
• 最終ジャッジ日時: 2024-07-02 05:57:40
• 合計ジャッジ時間: 16,790 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	161 ms; 28,928 KB
testcase_03	AC	42 ms; 5,376 KB
testcase_04	AC	186 ms; 32,000 KB
testcase_05	AC	144 ms; 27,776 KB
testcase_06	AC	148 ms; 28,800 KB
testcase_07	AC	39 ms; 5,376 KB
testcase_08	AC	171 ms; 34,688 KB
testcase_09	AC	155 ms; 31,872 KB
testcase_10	AC	127 ms; 20,480 KB
testcase_11	AC	94 ms; 28,416 KB
testcase_12	AC	104 ms; 28,416 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB

ソースコード

pub trait Magma: Sized + Clone {
  fn op(&self, rhs: &Self) -> Self;
}

pub trait Associative: Magma {}

pub trait Unital: Magma {
  fn identity() -> Self;
}

pub trait Monoid: Magma + Associative + Unital {}

impl<T: Magma + Associative + Unital> Monoid for T {}

pub struct Node<M: Monoid> {
    left: Option<Box<Self>>,
    right: Option<Box<Self>>,
    val: M,
}

impl<M: Monoid> Node<M> {
    fn new() -> Self {
        Node {
            left: None,
            right: None,
            val: M::identity(),
        }
    }
}

pub fn value<M: Monoid>(node: &Option<Box<Node<M>>>) -> M {
    match node.as_ref() {
        Some(n) => n.as_ref().val.clone(),
        None => M::identity()
    }
}

pub fn update_node<M: Monoid>(node: &mut Node<M>, i: usize, x: M, l: usize, r: usize) {
    if l + 1 == r {
        node.val = x;
    }
    else {
        let m = (l + r) >> 1;
        if i < m {
            {
                let left = match node.left.as_mut() {
                    Some(left) => left.as_mut(),
                    None => {
                        node.left = Some(Box::new(Node::new()));
                        node.left.as_mut().unwrap().as_mut()
                    }
                };
                update_node(left, i, x, l, m);
            }
        }
        else {
            {
                let right = match node.right.as_mut() {
                    Some(right) => right.as_mut(),
                    None => {
                        node.right = Some(Box::new(Node::new()));
                        node.right.as_mut().unwrap().as_mut()
                    }
                };
                update_node(right, i, x, m, r);
            }
        }
        node.val = value(&node.left).op(&value(&node.right));
    }
}

pub fn fold<M: Monoid>(node: &Node<M>, a: usize, b: usize, l: usize, r: usize) -> M {
    if a <= l && r <= b { node.val.clone() }
    else if r <= a || b <= l { M::identity() }
    else {
        match node.left.as_ref() {
            Some(le) => fold(le, a, b, l, (l + r) >> 1),
            None => M::identity(),
        }.op(& match node.right.as_ref() {
            Some(ri) => fold(ri, a, b, (l + r) >> 1, r),
            None => M::identity(),
        })
    }
}

pub struct DynamicSegmentTree<M: Monoid> {
    root: Node<M>,
    n: usize,
}

impl<M: Monoid> DynamicSegmentTree<M> {
    pub fn new(n: usize) -> Self {
        let mut sz = 1;
        while sz < n { sz = sz << 1; }
        DynamicSegmentTree {
            root: Node::new(),
            n: sz
        }
    }

    pub fn update(&mut self, i: usize, x: M) {
        update_node(&mut self.root, i, x, 0, self.n);
    }

    pub fn fold(&self, a: usize, b: usize) -> M {
        fold(&self.root, a, b, 0, self.n)
    }
}

#[derive(Clone)]
struct A(usize);

impl Magma for A {
    fn op(&self, a: &Self) -> Self { A(self.0 + a.0) }
}
impl Associative for A {}
impl Unital for A {
    fn identity() -> Self { A(0) }
}

use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let q: usize = iter.next().unwrap().parse().unwrap();
    let mut dyseg = DynamicSegmentTree::<A>::new(1_000_000_100);
    let mut ans = A(0);
    for _ in 0..q {
        let query: usize = iter.next().unwrap().parse().unwrap();
        let a: usize = iter.next().unwrap().parse().unwrap();
        let b: usize = iter.next().unwrap().parse().unwrap();
        if query == 0 {
            dyseg.update(a, dyseg.fold(a, a + 1).op(&A(b)));
        }
        else if query == 1 {
            ans = ans.op(&dyseg.fold(a, b + 1));
        }
    }
    println!("{}", ans.0);

}