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

• 問題: No.789 範囲の合計
• ユーザー: sakikuroe
• 提出日時: 2024-03-06 21:22:43
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 52 ms / 1,000 ms
• コード長: 3,269 bytes
• コンパイル時間: 19,694 ms
• コンパイル使用メモリ: 400,484 KB
• 実行使用メモリ: 6,912 KB
• 最終ジャッジ日時: 2024-09-29 18:36:16
• 合計ジャッジ時間: 20,543 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,820 KB
testcase_01	AC	1 ms; 6,816 KB
testcase_02	AC	51 ms; 6,816 KB
testcase_03	AC	30 ms; 6,820 KB
testcase_04	AC	49 ms; 6,820 KB
testcase_05	AC	37 ms; 6,816 KB
testcase_06	AC	39 ms; 6,816 KB
testcase_07	AC	26 ms; 6,816 KB
testcase_08	AC	41 ms; 6,912 KB
testcase_09	AC	37 ms; 6,816 KB
testcase_10	AC	52 ms; 6,820 KB
testcase_11	AC	34 ms; 6,816 KB
testcase_12	AC	33 ms; 6,820 KB
testcase_13	AC	1 ms; 6,816 KB
testcase_14	AC	1 ms; 6,816 KB

ソースコード

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,
    cordinate: Vec<usize>,
    data: Vec<M::S>,
}

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

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

    pub fn build(&mut self) {
        self.cordinate.sort();
        self.cordinate.dedup();
        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.binary_search(&idx).unwrap() + self.size - 1;
        self.data[idx].clone()
    }

    pub fn update(&mut self, mut idx: usize, x: M::S) {
        idx = self.cordinate.binary_search(&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.partition_point(|&x| x < l) + self.size - 1;
        r = self.cordinate.partition_point(|&x| x < 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);
}