結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー ガルム
提出日時 2026-04-18 13:46:06
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 1,084 ms / 2,000 ms
コード長 6,546 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,401 ms
コンパイル使用メモリ 195,260 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2026-04-18 13:46:44
合計ジャッジ時間 21,424 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::io::{self, Read};

fn isqrt(x: u64) -> u64 {
    let mut r = (x as f64).sqrt() as u64;
    while (r + 1) * (r + 1) <= x {
        r += 1;
    }
    while r * r > x {
        r -= 1;
    }
    r
}

fn push(values: &mut [u64], lazy: &mut [Option<u64>], starts: &[usize], ends: &[usize], b: usize) {
    if let Some(x) = lazy[b] {
        for v in &mut values[starts[b]..ends[b]] {
            *v = x;
        }
        lazy[b] = None;
    }
}

fn rebuild(
    values: &[u64],
    lazy: &mut [Option<u64>],
    sum: &mut [u64],
    max_value: &mut [u64],
    starts: &[usize],
    ends: &[usize],
    b: usize,
) {
    let mut s = 0_u64;
    let mut mx = 0_u64;
    let mut mn = u64::MAX;

    for &v in &values[starts[b]..ends[b]] {
        s += v;
        mx = mx.max(v);
        mn = mn.min(v);
    }

    sum[b] = s;
    max_value[b] = mx;
    lazy[b] = if mn == mx { Some(mx) } else { None };
}

fn apply_set(
    lazy: &mut [Option<u64>],
    sum: &mut [u64],
    max_value: &mut [u64],
    starts: &[usize],
    ends: &[usize],
    b: usize,
    x: u64,
) {
    lazy[b] = Some(x);
    sum[b] = x * (ends[b] - starts[b]) as u64;
    max_value[b] = x;
}

fn apply_sqrt_block(
    values: &mut [u64],
    lazy: &mut [Option<u64>],
    sum: &mut [u64],
    max_value: &mut [u64],
    starts: &[usize],
    ends: &[usize],
    b: usize,
) {
    if max_value[b] <= 1 {
        return;
    }

    if let Some(x) = lazy[b] {
        let y = isqrt(x);
        apply_set(lazy, sum, max_value, starts, ends, b, y);
        return;
    }

    for v in &mut values[starts[b]..ends[b]] {
        *v = isqrt(*v);
    }
    rebuild(values, lazy, sum, max_value, starts, ends, b);
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let n: usize = it.next().unwrap().parse().unwrap();
    let q: usize = it.next().unwrap().parse().unwrap();

    let block_size = 700_usize;
    let block_count = (n + block_size - 1) / block_size;
    let mut starts = vec![0_usize; block_count];
    let mut ends = vec![0_usize; block_count];
    for b in 0..block_count {
        starts[b] = b * block_size;
        ends[b] = ((b + 1) * block_size).min(n);
    }

    let mut values = vec![0_u64; n];
    for v in &mut values {
        *v = it.next().unwrap().parse().unwrap();
    }

    let mut lazy = vec![None; block_count];
    let mut sum = vec![0_u64; block_count];
    let mut max_value = vec![0_u64; block_count];
    for b in 0..block_count {
        rebuild(&values, &mut lazy, &mut sum, &mut max_value, &starts, &ends, b);
    }

    let mut out = String::new();

    for _ in 0..q {
        let ty: usize = it.next().unwrap().parse().unwrap();
        let l: usize = it.next().unwrap().parse().unwrap();
        let r: usize = it.next().unwrap().parse().unwrap();

        if l == r {
            if ty == 1 {
                let _: u64 = it.next().unwrap().parse().unwrap();
            } else if ty == 0 {
                out.push_str("0\n");
            }
            continue;
        }

        let lb = l / block_size;
        let rb = (r - 1) / block_size;

        match ty {
            0 => {
                let mut ans = 0_u64;
                if lb == rb {
                    if let Some(x) = lazy[lb] {
                        ans = x * (r - l) as u64;
                    } else {
                        ans = values[l..r].iter().sum();
                    }
                } else {
                    push(&mut values, &mut lazy, &starts, &ends, lb);
                    ans += values[l..ends[lb]].iter().sum::<u64>();
                    rebuild(&values, &mut lazy, &mut sum, &mut max_value, &starts, &ends, lb);

                    push(&mut values, &mut lazy, &starts, &ends, rb);
                    ans += values[starts[rb]..r].iter().sum::<u64>();
                    rebuild(&values, &mut lazy, &mut sum, &mut max_value, &starts, &ends, rb);

                    for b in lb + 1..rb {
                        ans += sum[b];
                    }
                }
                out.push_str(&format!("{}\n", ans));
            }
            1 => {
                let x: u64 = it.next().unwrap().parse().unwrap();
                if lb == rb {
                    push(&mut values, &mut lazy, &starts, &ends, lb);
                    values[l..r].fill(x);
                    rebuild(&values, &mut lazy, &mut sum, &mut max_value, &starts, &ends, lb);
                } else {
                    push(&mut values, &mut lazy, &starts, &ends, lb);
                    values[l..ends[lb]].fill(x);
                    rebuild(&values, &mut lazy, &mut sum, &mut max_value, &starts, &ends, lb);

                    push(&mut values, &mut lazy, &starts, &ends, rb);
                    values[starts[rb]..r].fill(x);
                    rebuild(&values, &mut lazy, &mut sum, &mut max_value, &starts, &ends, rb);

                    for b in lb + 1..rb {
                        apply_set(&mut lazy, &mut sum, &mut max_value, &starts, &ends, b, x);
                    }
                }
            }
            2 => {
                if lb == rb {
                    push(&mut values, &mut lazy, &starts, &ends, lb);
                    for v in &mut values[l..r] {
                        *v = isqrt(*v);
                    }
                    rebuild(&values, &mut lazy, &mut sum, &mut max_value, &starts, &ends, lb);
                } else {
                    push(&mut values, &mut lazy, &starts, &ends, lb);
                    for v in &mut values[l..ends[lb]] {
                        *v = isqrt(*v);
                    }
                    rebuild(&values, &mut lazy, &mut sum, &mut max_value, &starts, &ends, lb);

                    push(&mut values, &mut lazy, &starts, &ends, rb);
                    for v in &mut values[starts[rb]..r] {
                        *v = isqrt(*v);
                    }
                    rebuild(&values, &mut lazy, &mut sum, &mut max_value, &starts, &ends, rb);

                    for b in lb + 1..rb {
                        apply_sqrt_block(
                            &mut values,
                            &mut lazy,
                            &mut sum,
                            &mut max_value,
                            &starts,
                            &ends,
                            b,
                        );
                    }
                }
            }
            _ => unreachable!(),
        }
    }

    print!("{}", out);
}
0