結果

問題 No.789 範囲の合計
コンテスト
ユーザー niuez
提出日時 2019-07-25 10:38:52
言語 Rust
(1.83.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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);

}
0