#613251 (Rust) No.880 Yet Another Segment Tree Problem

• 問題: No.880 Yet Another Segment Tree Problem
• ユーザー: akakimidori
• 提出日時: 2021-02-05 16:21:49
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 233 ms / 5,000 ms
• コード長: 7,275 bytes
• コンパイル時間: 13,725 ms
• コンパイル使用メモリ: 382,540 KB
• 実行使用メモリ: 13,184 KB
• 最終ジャッジ日時: 2024-09-22 19:57:28
• 合計ジャッジ時間: 19,676 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	213 ms; 12,416 KB
testcase_12	AC	210 ms; 12,672 KB
testcase_13	AC	152 ms; 12,288 KB
testcase_14	AC	207 ms; 13,184 KB
testcase_15	AC	219 ms; 12,928 KB
testcase_16	AC	228 ms; 13,056 KB
testcase_17	AC	204 ms; 13,184 KB
testcase_18	AC	200 ms; 13,184 KB
testcase_19	AC	89 ms; 13,056 KB
testcase_20	AC	91 ms; 13,056 KB
testcase_21	AC	92 ms; 12,800 KB
testcase_22	AC	91 ms; 13,056 KB
testcase_23	AC	93 ms; 12,928 KB
testcase_24	AC	87 ms; 12,928 KB
testcase_25	AC	89 ms; 13,184 KB
testcase_26	AC	90 ms; 12,928 KB
testcase_27	AC	88 ms; 13,184 KB
testcase_28	AC	92 ms; 12,928 KB
testcase_29	AC	202 ms; 13,184 KB
testcase_30	AC	215 ms; 13,056 KB
testcase_31	AC	233 ms; 13,056 KB
testcase_32	AC	78 ms; 13,184 KB
testcase_33	AC	83 ms; 13,184 KB
testcase_34	AC	94 ms; 13,056 KB
testcase_35	AC	89 ms; 13,056 KB
testcase_36	AC	85 ms; 13,056 KB
testcase_37	AC	84 ms; 13,056 KB

ソースコード

pub trait Monoid: Sized {
    fn merge(&self, rhs: &Self) -> Self;
    fn e() -> Self;
    fn push(&mut self, c: &mut [Self]);
}

pub trait Effect<X> {
    fn break_cond(&self, x: &X) -> bool;
    fn tag_cond(&self, x: &X) -> bool;
    fn update(&self, x: &mut X);
}

pub struct SegmentTreeBeats<T> {
    size: usize,
    val: Box<[T]>,
    dfs: Vec<(usize, usize, usize)>,
}

impl<T: Monoid> SegmentTreeBeats<T> {
    pub fn update<E: Effect<T>>(&mut self, x: usize, y: usize, f: E) {
        assert!(x <= y && y <= self.size);
        if x >= y {
            return;
        }
        let val = &mut self.val;
        self.dfs.push((1, 0, self.size));
        while let Some((k, l, r)) = self.dfs.pop() {
            if k > 2 * self.size {
                let k = !k;
                val[k] = val[2 * k].merge(&val[2 * k + 1]);
                continue;
            }
            if f.break_cond(&val[k]) {
                continue;
            }
            if x <= l && r <= y && f.tag_cond(&val[k]) {
                f.update(&mut val[k]);
                continue;
            }
            let (a, b) = val.split_at_mut(2 * k);
            a[k].push(&mut b[..2]);
            self.dfs.push((!k, l, r));
            let m = (l + r) / 2;
            if m < y {
                self.dfs.push((2 * k + 1, m, r));
            }
            if x < m {
                self.dfs.push((2 * k, l, m));
            }
        }
    }
    pub fn find(&mut self, x: usize, y: usize) -> T {
        assert!(x <= y && y <= self.size);
        let mut res = T::e();
        if x >= y {
            return res;
        }
        let val = &mut self.val;
        self.dfs.push((1, 0, self.size));
        while let Some((k, l, r)) = self.dfs.pop() {
            if x <= l && r <= y {
                res = res.merge(&val[k]);
                continue;
            }
            let (a, b) = val.split_at_mut(2 * k);
            a[k].push(&mut b[..2]);
            let m = (l + r) / 2;
            if m < y {
                self.dfs.push((2 * k + 1, m, r));
            }
            if x < m {
                self.dfs.push((2 * k, l, m));
            }
        }
        res
    }
}

impl<T: Monoid + Clone> SegmentTreeBeats<T> {
    pub fn build(a: &[T]) -> Self {
        let size = a.len().next_power_of_two();
        let val = vec![T::e(); 2 * size];
        let mut val = val.into_boxed_slice();
        val[size..(size + a.len())].clone_from_slice(a);
        for i in (1..size).rev() {
            val[i] = val[2 * i].merge(&val[2 * i + 1]);
        }
        SegmentTreeBeats {
            size,
            val,
            dfs: vec![],
        }
    }
}
// end おためしbeats
// ---------- begin binary_gcd ----------
pub fn gcd(a: u64, b: u64) -> u64 {
    if a == 0 || b == 0 {
        return a + b;
    }
    let x = a.trailing_zeros();
    let y = b.trailing_zeros();
    let mut a = a >> x;
    let mut b = b >> y;
    while a != b {
         let x = (a ^ b).trailing_zeros();
        if a < b {
            std::mem::swap(&mut a, &mut b);
        }
        a = (a - b) >> x;
    }
    a << x.min(y)
}
// ---------- end binary_gcd ----------
// ---------- begin Scanner(require delimiter) ----------
mod scanner {
    pub struct Scanner<R> {
        reader: R,
        buf: Vec<u8>,
    }
    #[allow(dead_code)]
    impl<R: std::io::BufRead> Scanner<R> {
        pub fn new(reader: R) -> Self {
            Scanner {
                reader: reader,
                buf: Vec::with_capacity(1024),
            }
        }
        fn read(&mut self, del: u8) {
            self.buf.clear();
            self.reader.read_until(del, &mut self.buf).ok();
            assert!(self.buf.pop().unwrap() == del);
        }
        pub fn next<T: std::str::FromStr>(&mut self, del: u8) -> T {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .parse::<T>()
                .ok()
                .unwrap()
        }
        pub fn next_bytes(&mut self, del: u8) -> Vec<u8> {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .bytes()
                .collect()
        }
    }
}
// ---------- end scanner(require delimiter) ----------

use std::io::Write;

fn main() {
    let stdin = std::io::stdin();
    let mut sc = scanner::Scanner::new(stdin.lock());
    run(&mut sc);
}

const INF: u64 = 1_000_000_000 + 1;

fn lcm(a: u64, b: u64) -> u64 {
    if a >= INF || b >= INF {
        return INF;
    }
    let g = gcd(a, b);
    INF.min(a * b / g)
}

#[derive(Clone)]
struct Value {
    lcm: u64,
    max: u64,
    sum: u64,
    len: u64,
}

impl Monoid for Value {
    fn merge(&self, rhs: &Self) -> Self {
        Self {
            lcm: lcm(self.lcm, rhs.lcm),
            max: self.max.max(rhs.max),
            sum: self.sum + rhs.sum,
            len: self.len + rhs.len,
        }
    }
    fn e() -> Self {
        Self {
            lcm: 1,
            max: 0,
            sum: 0,
            len: 0,
        }
    }
    fn push(&mut self, c: &mut [Self]) {
        let v = self.max;
        if v * self.len == self.sum {
            for c in c.iter_mut() {
                c.assign(v);
            }
        }
    }
}

impl Value {
    fn assign(&mut self, v: u64) {
        self.lcm = v;
        self.max = v;
        self.sum = self.len * v;
    }
}

struct Chgcd(u64);
impl Effect<Value> for Chgcd {
    fn break_cond(&self, x: &Value) -> bool {
        self.0 % x.lcm == 0
    }
    fn tag_cond(&self, x: &Value) -> bool {
        x.max * x.len == x.sum
    }
    fn update(&self, x: &mut Value) {
        let v = gcd(self.0, x.max);
        x.assign(v);
    }
}

struct Set(u64);
impl Effect<Value> for Set {
    fn break_cond(&self, _: &Value) -> bool {
        false
    }
    fn tag_cond(&self, _: &Value) -> bool {
        true
    }
    fn update(&self, x: &mut Value) {
        x.assign(self.0);
    }
}

fn run<R: std::io::BufRead>(sc: &mut scanner::Scanner<R>) {
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    let n: usize = sc.next(b' ');
    let q: usize = sc.next(b'\n');
    let mut ini = Vec::with_capacity(n);
    for i in 0..n {
        let d = if i == n - 1 {b'\n'} else {b' '};
        let v: u64 = sc.next(d);
        ini.push(Value {
            lcm: v,
            max: v,
            sum: v,
            len: 1,
        });
    }
    let mut seg = SegmentTreeBeats::build(&ini);
    for _ in 0..q {
        let op: u8 = sc.next(b' ');
        let (l, r, x) = if op <= 2 {
            let l: usize = sc.next(b' ');
            let r: usize = sc.next(b' ');
            let x: u64 = sc.next(b'\n');
            (l - 1, r, x)
        } else {
            let l: usize = sc.next(b' ');
            let r: usize = sc.next(b'\n');
            (l - 1, r, 0)
        };
        if op == 1 {
            seg.update(l, r, Set(x));
        } else if op == 2 {
            seg.update(l, r, Chgcd(x));
        } else if op == 3 {
            let ans = seg.find(l, r).max;
            writeln!(out, "{}", ans).ok();
        } else {
            let ans = seg.find(l, r).sum;
            writeln!(out, "{}", ans).ok();
        }
    }
}