verification/library-checker/point_set_range_composite/src/main.rs

• View this file on GitHub
• Last update: 2026-01-01 00:11:18+09:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_composite

Depends on

• Segment Tree (data-structure/segment-tree/src/lib.rs)
• Segment Tree (Wrapper) (data-structure/segment-tree/src/wrapper.rs)
• macro/query/src/lib.rs
• Modint (math/modint/src/lib.rs)

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/point_set_range_composite

use proconio::input;

use modint::StaticModint;
use segment_tree::SegmentTree;

type Mint = StaticModint<998244353>;

query::define_query! {
    Query {
        0 => Query0(p: usize, c: u64, d: u64),
        1 => Query1(l: usize, r: usize, x: u64),
    }
}

fn main() {
    input! {
        n: usize,
        q: usize,
        ab: [(u64, u64); n],
        queries: [Query; q],
    }
    let mut st = SegmentTree::<(Mint, Mint)>::new(n, |x, y| (x.0 * y.0, x.1 * y.0 + y.1), (Mint::new(1), Mint::new(0)));
    let ab = ab.iter().map(|&(a, b)| (Mint::new(a), Mint::new(b))).collect::<Vec<_>>();
    st.build(&ab);

    for query in queries {
        match query {
            Query0(p, c, d) => st.set(p, (Mint::new(c), Mint::new(d))),
            Query1(l, r, x) => {
                let (a, b) = st.prod(l, r);
                println!("{}", Mint::new(x) * a + b);
            }
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
Rust	example_00	AC	6 ms	2 MB
Rust	max_random_00	AC	605 ms	49 MB
Rust	max_random_01	AC	597 ms	49 MB
Rust	max_random_02	AC	621 ms	49 MB
Rust	max_random_03	AC	610 ms	49 MB
Rust	max_random_04	AC	615 ms	50 MB
Rust	random_00	AC	489 ms	43 MB
Rust	random_01	AC	555 ms	46 MB
Rust	random_02	AC	365 ms	18 MB
Rust	random_03	AC	91 ms	33 MB
Rust	random_04	AC	143 ms	30 MB
Rust	small_00	AC	6 ms	2 MB
Rust	small_01	AC	6 ms	2 MB
Rust	small_02	AC	6 ms	2 MB
Rust	small_03	AC	6 ms	2 MB
Rust	small_04	AC	6 ms	2 MB

Back to top page