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

• 問題: No.880 Yet Another Segment Tree Problem
• ユーザー: akakimidori
• 提出日時: 2021-08-23 18:49:41
• 言語: Rust (1.83.0 + proconio)
• 結果: TLE
• 実行時間: -
• コード長: 6,814 bytes
• コンパイル時間: 15,007 ms
• コンパイル使用メモリ: 383,228 KB
• 実行使用メモリ: 19,772 KB
• 最終ジャッジ日時: 2024-11-07 21:33:20
• 合計ジャッジ時間: 29,236 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 1
other	AC * 32 TLE * 1 -- * 4

ソースコード

// ---------- begin binary_gcd ----------
pub fn binary_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 ----------

pub trait DFSTest: Clone {
    fn merge(&mut self, l: &Self, r: &Self);
    fn propagate(&mut self, c: &mut [Self]);
}

struct SegmentTree<T> {
    data: Vec<T>,
    size: usize,
    stack: Vec<(usize, usize, usize)>,
}

impl<T> SegmentTree<T>
where
    T: DFSTest,
{
    fn new(ini: Vec<T>) -> Self {
        let size = ini.len().next_power_of_two();
        let mut data = vec![ini[0].clone(); 2 * size];
        for (data, ini) in data[size..].iter_mut().zip(ini) {
            *data = ini;
        }
        for i in (1..size).rev() {
            let (f, t) = data.split_at_mut(2 * i);
            f[i].merge(&t[0], &t[1]);
        }
        Self {
            data,
            size,
            stack: vec![],
        }
    }
    fn update_bool<F>(&mut self, l: usize, r: usize, mut f: F)
    where
        F: FnMut(&mut T) -> bool,
    {
        self.stack.clear();
        self.stack.push((1, 0, self.size));
        while let Some((v, x, y)) = self.stack.pop() {
            if v >= 2 * self.size {
                let v = !v;
                let (f, t) = self.data.split_at_mut(2 * v);
                f[v].merge(&t[0], &t[1]);
                continue;
            }
            if l <= x && y <= r && f(&mut self.data[v]) {
                continue;
            }
            assert!(v < self.size);
            {
                let (f, t) = self.data.split_at_mut(2 * v);
                f[v].propagate(&mut t[..2]);
            }
            let mid = (x + y) / 2;
            self.stack.push((!v, x, y));
            if mid < r {
                self.stack.push((2 * v + 1, mid, y));
            }
            if l < mid {
                self.stack.push((2 * v, x, mid));
            }
        }
    }
    fn update<F>(&mut self, l: usize, r: usize, mut f: F)
    where
        F: FnMut(&mut T)
    {
        self.update_bool(l, r, |node| {
            f(node);
            true
        });
    }
    fn query<F>(&mut self, l: usize, r: usize, mut f: F)
    where
        F: FnMut(&T),
    {
        self.stack.clear();
        self.stack.push((1, 0, self.size));
        while let Some((v, x, y)) = self.stack.pop() {
            if l <= x && y <= r {
                f(&self.data[v]);
                continue;
            }
            assert!(v < self.size);
            {
                let (f, t) = self.data.split_at_mut(2 * v);
                f[v].propagate(&mut t[..2]);
            }
            let mid = (x + y) / 2;
            if mid < r {
                self.stack.push((2 * v + 1, mid, y));
            }
            if l < mid {
                self.stack.push((2 * v, x, mid));
            }
        }
    }
}

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

impl Node {
    fn assign(&mut self, x: u64) {
        self.sum = self.len * x;
        self.max = x;
        self.lcm = x;
    }
    fn chgcd(&mut self, x: u64) {
        assert!(self.max * self.len == self.sum);
        let g = binary_gcd(x, self.max);
        self.assign(g);
    }
}

const UPPER: u64 = 1_000_000_000 + 1;

impl DFSTest for Node {
    fn merge(&mut self, l: &Self, r: &Self) {
        self.sum = l.sum + r.sum;
        self.max = l.max.max(r.max);
        self.len = l.len + r.len;
        self.lcm = UPPER.min(l.lcm * r.lcm / binary_gcd(l.lcm, r.lcm));
    }
    fn propagate(&mut self, c: &mut [Self]) {
        if self.max * self.len == self.sum {
            for c in c.iter_mut() {
                c.assign(self.max);
            }
        }
    }
}

// ---------- 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);
}


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(Node {
            sum: v,
            max: v,
            lcm: v,
            len: 1,
        });
    }
    let mut seg = SegmentTree::new(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, |node| node.assign(x));
        } else if op == 2 {
            seg.update_bool(l, r, |node| {
                node.max * node.len == node.sum && {
                    node.chgcd(x);
                    true
                }
            });
        } else if op == 3 {
            let mut ans = 0;
            seg.query(l, r, |node| ans = ans.max(node.max));
            writeln!(out, "{}", ans).ok();
        } else {
            let mut ans = 0;
            seg.query(l, r, |node| ans += node.sum);
            writeln!(out, "{}", ans).ok();
        }
    }
}