結果

問題 No.789 範囲の合計
ユーザー niuezniuez
提出日時 2019-07-25 15:58:00
言語 Rust
(1.77.0)
結果
AC  
実行時間 73 ms / 1,000 ms
コード長 4,705 bytes
コンパイル時間 583 ms
コンパイル使用メモリ 141,388 KB
実行使用メモリ 9,952 KB
最終ジャッジ日時 2023-09-14 23:53:19
合計ジャッジ時間 2,175 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 69 ms
8,596 KB
testcase_03 AC 61 ms
4,380 KB
testcase_04 AC 73 ms
9,160 KB
testcase_05 AC 56 ms
8,352 KB
testcase_06 AC 58 ms
8,632 KB
testcase_07 AC 65 ms
4,380 KB
testcase_08 AC 65 ms
9,952 KB
testcase_09 AC 59 ms
9,184 KB
testcase_10 AC 58 ms
7,020 KB
testcase_11 AC 47 ms
7,856 KB
testcase_12 AC 49 ms
7,764 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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 enum Node<T: Monoid> {
    Section(Box<Section<T>>),
    Leaf(Leaf<T>),
    None,
}

pub struct Section<T: Monoid> {
    left: Node<T>,
    right: Node<T>,
    val: T,
}

pub struct Leaf<T: Monoid> {
    i: usize,
    val: T,
}

impl<T: Monoid> Leaf<T> {
    fn new(i: usize, x: T) -> Self {
        Leaf { i: i, val: x }
    }
    fn fold(&self) -> T { self.val.clone() }
}

impl<T: Monoid> Section<T> {
    fn new() -> Self {
        Section {
            left: Node::None,
            right: Node::None,
            val: T::identity(),
        }
    }
    fn fold(&self) -> T { self.val.clone() }
    fn update(&mut self, i: usize, x: T, l: usize, r: usize) {
        let m = (l + r) >> 1;
        if i < m {
            let left = self.left.take();
            self.left = left.update(i, x, l, m);
        }
        else {
            let right = self.right.take();
            self.right = right.update(i, x, m, r);
        }
        self.val = self.left.fold().op(&self.right.fold());
    }
}

impl<T: Monoid> Node<T> {
    fn take(&mut self) -> Node<T> {
        std::mem::replace(self, Node::None)
    }
    fn fold(&self) -> T {
        match self {
            &Node::Section(ref sec) => sec.as_ref().fold(),
            &Node::Leaf(ref leaf) => leaf.fold(),
            &Node::None => T::identity(),
        }
    }
    fn update(self, i: usize, x: T, l: usize, r: usize) -> Self {
        match self {
            Node::Section(mut sec) => {
                sec.as_mut().update(i, x, l, r);
                Node::Section(sec)
            }
            Node::Leaf(leaf) => {
                if leaf.i == i {
                    Node::Leaf(Leaf::new(i, x))
                }
                else {
                    let mut new_section = Section::new();
                    let m = (l + r) >> 1;
                    if leaf.i < m {
                        new_section.left = Node::Leaf(leaf);
                    }
                    else {
                        new_section.right = Node::Leaf(leaf);
                    }
                    new_section.update(i, x, l, r);
                    Node::Section(Box::new(new_section))
                }
            }
            Node::None => {
                Node::Leaf(Leaf::new(i, x))
            }
        }
    }
    fn range_fold(&self, a: usize, b: usize, l: usize, r: usize) -> T {
        match self {
            &Node::Section(ref sec) => {
                if b <= l || r <= a { T::identity() }
                else if a <= l && r <= b { sec.fold() }
                else {
                    let m = (l + r) >> 1;
                    sec.left.range_fold(a, b, l, m).op(&sec.right.range_fold(a, b, m, r))
                }
            }
            &Node::Leaf(ref leaf) => {
                if a <= leaf.i && leaf.i < b { leaf.fold() }
                else { T::identity() }
            }
            &Node::None => T::identity(),
        }
    }
}

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

impl<T: Monoid> DynamicSegmentTree<T> {
    pub fn new(sz: usize) -> Self {
        let mut n = 1;
        while n < sz { n = n << 1; }
        DynamicSegmentTree {
            root: Node::None,
            n: n,
        }
    }
    pub fn update(&mut self, i: usize, x: T) {
        let r = self.root.take();
        self.root = r.update(i, x, 0,  self.n);
    }
    pub fn fold(&self, l: usize, r: usize) -> T {
        self.root.range_fold(l, r, 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 {
            let val = dyseg.fold(a, a + 1).op(&A(b));
            dyseg.update(a, val);
        }
        else if query == 1 {
            ans = ans.op(&dyseg.fold(a, b + 1));
        }
    }
    println!("{}", ans.0);

}
0