結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー akakimidoriakakimidori
提出日時 2020-10-26 17:17:33
言語 Rust
(1.77.0)
結果
AC  
実行時間 421 ms / 5,000 ms
コード長 7,298 bytes
コンパイル時間 4,353 ms
コンパイル使用メモリ 177,160 KB
実行使用メモリ 13,208 KB
最終ジャッジ日時 2023-10-24 02:50:05
合計ジャッジ時間 9,439 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,372 KB
testcase_01 AC 2 ms
4,372 KB
testcase_02 AC 2 ms
4,372 KB
testcase_03 AC 2 ms
4,372 KB
testcase_04 AC 2 ms
4,372 KB
testcase_05 AC 1 ms
4,372 KB
testcase_06 AC 1 ms
4,372 KB
testcase_07 AC 2 ms
4,372 KB
testcase_08 AC 2 ms
4,372 KB
testcase_09 AC 2 ms
4,372 KB
testcase_10 AC 2 ms
4,372 KB
testcase_11 AC 374 ms
12,484 KB
testcase_12 AC 367 ms
12,484 KB
testcase_13 AC 258 ms
12,220 KB
testcase_14 AC 372 ms
12,944 KB
testcase_15 AC 399 ms
12,944 KB
testcase_16 AC 417 ms
12,944 KB
testcase_17 AC 337 ms
13,208 KB
testcase_18 AC 345 ms
13,208 KB
testcase_19 AC 104 ms
12,944 KB
testcase_20 AC 108 ms
13,208 KB
testcase_21 AC 107 ms
12,944 KB
testcase_22 AC 113 ms
12,944 KB
testcase_23 AC 110 ms
12,944 KB
testcase_24 AC 95 ms
12,944 KB
testcase_25 AC 100 ms
13,208 KB
testcase_26 AC 100 ms
12,944 KB
testcase_27 AC 100 ms
12,944 KB
testcase_28 AC 102 ms
12,944 KB
testcase_29 AC 367 ms
12,944 KB
testcase_30 AC 395 ms
12,944 KB
testcase_31 AC 421 ms
12,944 KB
testcase_32 AC 80 ms
13,208 KB
testcase_33 AC 85 ms
12,944 KB
testcase_34 AC 90 ms
12,944 KB
testcase_35 AC 86 ms
12,944 KB
testcase_36 AC 87 ms
12,944 KB
testcase_37 AC 87 ms
12,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// begin おためしbeats
pub trait Beats {
    type Value: Clone;
    type Query;
    fn merge(l: &Self::Value, r: &Self::Value) -> Self::Value;
    fn break_cond(x: &Self::Value, f: &Self::Query) -> bool;
    fn tag_cond(x: &Self::Value, f: &Self::Query) -> bool;
    fn update(x: &mut Self::Value, f: &Self::Query);
    fn propagate(p: &mut Self::Value, c: &mut [Self::Value]);
    fn e() -> Self::Value;
}

struct SegmentTreeBeats<R: Beats> {
    size: usize,
    val: Box<[R::Value]>,
    dfs: Vec<(usize, usize, usize)>,
}

impl<R: Beats> SegmentTreeBeats<R> {
    fn new(ini: &[R::Value]) -> Self {
        let size = ini.len().next_power_of_two();
        let val = vec![R::e(); 2 * size];
        let mut val = val.into_boxed_slice();
        val[size..(size + ini.len())].clone_from_slice(ini);
        for i in (1..size).rev() {
            val[i] = R::merge(&val[2 * i], &val[2 * i + 1]);
        }
        SegmentTreeBeats {
            size,
            val,
            dfs: vec![],
        }
    }
    fn update(&mut self, x: usize, y: usize, f: &R::Query) {
        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] = R::merge(&val[2 * k], &val[2 * k + 1]);
                continue;
            }
            if R::break_cond(&val[k], f) {
                continue;
            }
            if x <= l && r <= y && R::tag_cond(&val[k], f) {
                R::update(&mut val[k], f);
                continue;
            }
            let (a, b) = val.split_at_mut(2 * k);
            R::propagate(&mut a[k], &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));
            }
        }
    }
    fn find(&mut self, x: usize, y: usize) -> R::Value {
        assert!(x <= y && y <= self.size);
        let mut res = R::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 = R::merge(&res, &val[k]);
                continue;
            }
            let (a, b) = val.split_at_mut(2 * k);
            R::propagate(&mut a[k], &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
    }
}
// end おためしbeats
// ---------- 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 gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

const INF: u64 = 1_000_000_000 + 1;

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

enum Update {
    Set(u64),
    Chgcd(u64),
}

struct Yuki880;
impl Beats for Yuki880 {
    type Value = Value;
    type Query = Update;
    fn merge(l: &Self::Value, r: &Self::Value) -> Self::Value {
        Value {
            lcm: std::cmp::min(INF, l.lcm * r.lcm / gcd(l.lcm, r.lcm)),
            max: std::cmp::max(l.max, r.max),
            sum: l.sum + r.sum,
            len: l.len + r.len,
        }
    }
    fn break_cond(x: &Self::Value, f: &Self::Query) -> bool {
        match *f {
            Update::Set(_) => false,
            Update::Chgcd(ref y) => y % x.lcm == 0,
        }
    }
    fn tag_cond(x: &Self::Value, f: &Self::Query) -> bool {
        match *f {
            Update::Set(_) => true,
            Update::Chgcd(_) => x.sum == x.max * x.len,
        }
    }
    fn update(x: &mut Self::Value, f: &Self::Query) {
        match *f {
            Update::Set(ref v) => {
                x.lcm = *v;
                x.max = *v;
                x.sum = *v * x.len;
            },
            Update::Chgcd(ref y) => {
                let v = gcd(*y, x.max);
                x.lcm = v;
                x.max = v;
                x.sum = v * x.len;
            },
        }
    }
    fn propagate(p: &mut Self::Value, c: &mut [Self::Value]) {
        let v = p.max;
        if v * p.len == p.sum {
            for c in c.iter_mut() {
                c.lcm = v;
                c.max = v;
                c.sum = v * c.len;
            }
        }
    }
    fn e() -> Self::Value {
        Value {
            lcm: 1,
            max: 0,
            sum: 0,
            len: 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::<Yuki880>::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, &Update::Set(x));
        } else if op == 2 {
            seg.update(l, r, &Update::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();
        }
    }
}
0