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

• 問題: No.789 範囲の合計
• ユーザー: sakikuroe
• 提出日時: 2024-03-06 17:23:36
• 言語: Rust (1.83.0 + proconio)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 3,643 bytes
• コンパイル時間: 36 ms
• 最終ジャッジ日時: 2024-09-29 18:16:54
• 合計ジャッジ時間: 1,499 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

コンパイルメッセージ

230be1473c3c
[/j_bin/judge_tool judge 0 30000 ../CompileMemory.txt /dev/null sud /dev/null _ /usr/bin/rustc_custom]
open /home/yuki2006/gopath/src/yukicoder/judge/lang/lang.csv: no such file or directory
goroutine 1 [running]:
runtime/debug.Stack()
	/usr/local/go/src/runtime/debug/stack.go:24 +0x5e
main.main.func1()
	/home/yuki2006/gopath/src/yukicoder/judge/main.go:20 +0x57
panic({0x7661e0?, 0xc000070b70?})
	/usr/local/go/src/runtime/panic.go:770 +0x132
yukicoder/env.InitLangCommands(0x0)
	/home/yuki2006/gopath/src/yukicoder/env/lang.go:57 +0x3a5
main.main()
	/home/yuki2006/gopath/src/yukicoder/judge/main.go:42 +0x65

ソースコード

use std::collections::BTreeMap;

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

pub struct SegmentTreeSparseStatic<M>
where
    M: Monoid,
{
    size: usize,
    points: Vec<usize>,
    cordinate: BTreeMap<usize, usize>,
    data: Vec<M::S>,
}

impl<M> SegmentTreeSparseStatic<M>
where
    M: Monoid,
    M::S: Clone,
{
    pub fn new() -> Self {
        SegmentTreeSparseStatic::<M> {
            size: 0,
            points: vec![],
            cordinate: BTreeMap::new(),
            data: vec![],
        }
    }

    pub fn point_add(&mut self, idx: usize) {
        self.points.push(idx);
    }

    pub fn build(&mut self) {
        let mut o = self.points.iter().cloned().collect::<Vec<_>>();
        o.sort();
        o.dedup();
        self.cordinate = (0..o.len()).map(|i| (o[i], i)).collect();
        self.size = self.cordinate.len().next_power_of_two();
        self.data.resize(2 * self.size - 1, M::id());
    }

    pub fn get(&self, mut idx: usize) -> M::S {
        idx = *self.cordinate.get(&idx).unwrap();
        idx += self.size - 1;
        self.data[idx].clone()
    }

    pub fn update(&mut self, mut idx: usize, x: M::S) {
        idx = *self.cordinate.get(&idx).unwrap();
        idx += self.size - 1;
        self.data[idx] = x;
        while idx > 0 {
            idx = (idx - 1) / 2;
            self.data[idx] = M::op(&self.data[2 * idx + 1], &self.data[2 * idx + 2]);
        }
    }

    pub fn fold(&self, mut l: usize, mut r: usize) -> M::S {
        l = *self
            .cordinate
            .range(&l..)
            .next()
            .map(|x| x.1)
            .unwrap_or(&self.size);
        r = *self
            .cordinate
            .range(&r..)
            .next()
            .map(|x| x.1)
            .unwrap_or(&self.size);
        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[l]);
            }
            if r % 2 == 0 {
                sum_r = M::op(&self.data[r - 1], &sum_r);
            }
            l = l / 2;
            r = (r - 1) / 2;
        }

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

fn main() {
    let n;
    {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let mut ws = s.split_whitespace();
        n = ws.next().unwrap().parse::<usize>().unwrap();
    }

    let query;
    {
        let mut res: Vec<_> = vec![];
        for _ in 0..n {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            let mut ws = s.split_whitespace();
            res.push((
                ws.next().unwrap().parse::<usize>().unwrap(),
                ws.next().unwrap().parse::<usize>().unwrap(),
                ws.next().unwrap().parse::<usize>().unwrap(),
            ));
        }
        query = res;
    }

    let mut seg = SegmentTreeSparseStatic::<AddMonoid>::new();

    for i in 0..n {
        let (q, x, _) = query[i];
        if q == 0 {
            seg.point_add(x);
        }
    }

    seg.build();

    let mut ans = 0;
    for i in 0..n {
        let (q, x, y) = query[i];
        if q == 0 {
            let a = seg.get(x);
            seg.update(x, a + y);
        } else {
            ans += seg.fold(x, y + 1);
        }
    }

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