結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー akakimidori
提出日時 2020-02-27 23:50:14
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 4,547 bytes
記録
コンパイル時間 18,527 ms
コンパイル使用メモリ 391,544 KB
実行使用メモリ 15,116 KB
最終ジャッジ日時 2024-10-13 16:05:01
合計ジャッジ時間 20,860 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 16 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::io::Read;
use std::io::Write;
use std::cmp::*;

const INF: u64 = 1_000_000_000 + 1;

fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn lcm(a: u64, b: u64) -> u64 {
    assert!(a > 0 && b > 0);
    a / gcd(a, b) * b
}

struct Value {
    sum: u64,
    laz: u64,
    lcm: u64,
    max: u64,
    len: u64,
}

impl Value {
    fn new(val: u64) -> Self {
        Value {
            sum: val,
            laz: 0,
            lcm: val,
            max: val,
            len: 1,
        }
    }
    fn get_sum(&self) -> u64 {
        self.sum
    }
    fn get_max(&self) -> u64 {
        self.max
    }
    fn assign(&mut self, val: u64) {
        self.laz = val;
        self.sum = val * self.len;
        self.lcm = val;
        self.max = val;
    }
    fn fold(&self, rhs: &Self) -> Self {
        Value {
            sum: self.sum + rhs.sum,
            laz: 0,
            lcm: min(INF, lcm(self.lcm, rhs.lcm)),
            max: max(self.max, rhs.max),
            len: self.len + rhs.len,
        }
    }
    fn chgcd_break(&self, val: u64) -> bool {
        self.lcm != INF && val % self.lcm == 0
    }
    fn tag(&self) -> bool {
        self.laz > 0
    }
    fn chgcd(&mut self, val: u64) {
        assert!(self.laz > 0);
        let v = gcd(self.laz, val);
        self.assign(v);
    }
}

fn update(seg: &mut [Value], k: usize) {
    seg[k] = seg[2 * k].fold(&seg[2 * k + 1])
}

fn propagate(seg: &mut [Value], k: usize) {
    let v = seg[k].laz;
    seg[k].laz = 0;
    if v > 0 {
        seg[2 * k].assign(v);
        seg[2 * k + 1].assign(v);
    }
}

fn update_assign(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: u64) {
    if r <= x || y <= l {
        return;
    }
    if x <= l && r <= y {
        seg[k].assign(val);
        return;
    }
    propagate(seg, k);
    let m = (l + r) / 2;
    update_assign(seg, 2 * k, l, m, x, y, val);
    update_assign(seg, 2 * k + 1, m, r, x, y, val);
    update(seg, k);
}

fn update_chgcd(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: u64) {
    if r <= x || y <= l || seg[k].chgcd_break(val) {
        return;
    }
    if seg[k].tag() {
        seg[k].chgcd(val);
        return;
    }
    propagate(seg, k);
    let m = (l + r) / 2;
    update_chgcd(seg, 2 * k, l, m, x, y, val);
    update_chgcd(seg, 2 * k + 1, m, r, x, y, val);
    update(seg, k);
}

fn find_max(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize) -> u64 {
    if r <= x || y <= l {
        0
    } else if x <= l && r <= y {
        seg[k].get_max()
    } else {
        propagate(seg, k);
        let m = (l + r) / 2;
        max(find_max(seg, 2 * k, l, m, x, y), find_max(seg, 2 * k + 1, m, r, x, y))
    }
}

fn find_sum(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize) -> u64 {
    if r <= x || y <= l {
        0
    } else if x <= l && r <= y {
        seg[k].get_sum()
    } else {
        propagate(seg, k);
        let m = (l + r) / 2;
        find_sum(seg, 2 * k, l, m, x, y) + find_sum(seg, 2 * k + 1, m, r, x, y)
    }
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let q: usize = it.next().unwrap().parse().unwrap();
    let size = n.next_power_of_two();
    let mut seg: Vec<_> = (0..(2 * size)).map(|_| Value::new(1)).collect();
    for s in seg[size..].iter_mut().take(n) {
        s.assign(it.next().unwrap().parse().unwrap());
    }
    for i in (1..size).rev() {
        update(&mut seg, i);
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for _ in 0..q {
        let op: usize = it.next().unwrap().parse().unwrap();
        let l: usize = it.next().unwrap().parse().unwrap();
        let r: usize = it.next().unwrap().parse().unwrap();
        if op == 1 {
            let x: u64 = it.next().unwrap().parse().unwrap();
            update_assign(&mut seg, 1, 0, size, l - 1, r, x);
        } else if op == 2 {
            let x: u64 = it.next().unwrap().parse().unwrap();
            update_chgcd(&mut seg, 1, 0, size, l - 1, r, x);
        } else if op == 3 {
            let ans = find_max(&mut seg, 1, 0, size, l - 1, r);
            writeln!(out, "{}", ans).ok();
        } else {
            let ans = find_sum(&mut seg, 1, 0, size, l - 1, r);
            writeln!(out, "{}", ans).ok();
        }
    }
}

fn main() {
    run();
}
0