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

• 問題: No.789 範囲の合計
• ユーザー: sakikuroe
• 提出日時: 2024-03-06 17:27:08
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 62 ms / 1,000 ms
• コード長: 3,697 bytes
• コンパイル時間: 2,059 ms
• コンパイル使用メモリ: 208,912 KB
• 実行使用メモリ: 8,644 KB
• 最終ジャッジ日時: 2026-02-23 12:38:33
• 合計ジャッジ時間: 3,777 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

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

ソースコード

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() + self.size - 1;
        self.data[idx].clone()
    }

    pub fn update(&mut self, mut idx: usize, x: M::S) {
        idx = *self.cordinate.get(&idx).unwrap() + 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 {
        if l >= r {
            return M::id();
        }

        l = *self
            .cordinate
            .range(&l..)
            .next()
            .map(|x| x.1)
            .unwrap_or(&self.size)
            + self.size
            - 1;
        r = *self
            .cordinate
            .range(&r..)
            .next()
            .map(|x| x.1)
            .unwrap_or(&self.size)
            + 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);
}