結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー akakimidoriakakimidori
提出日時 2021-09-06 05:17:47
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 274 ms / 5,000 ms
コード長 6,530 bytes
コンパイル時間 14,125 ms
コンパイル使用メモリ 379,172 KB
実行使用メモリ 13,256 KB
最終ジャッジ日時 2024-09-22 19:58:58
合計ジャッジ時間 19,178 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 3 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 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 274 ms
12,416 KB
testcase_12 AC 214 ms
12,580 KB
testcase_13 AC 154 ms
12,284 KB
testcase_14 AC 209 ms
13,056 KB
testcase_15 AC 230 ms
13,116 KB
testcase_16 AC 241 ms
13,056 KB
testcase_17 AC 184 ms
13,184 KB
testcase_18 AC 183 ms
13,256 KB
testcase_19 AC 108 ms
13,056 KB
testcase_20 AC 110 ms
13,216 KB
testcase_21 AC 113 ms
12,928 KB
testcase_22 AC 103 ms
12,928 KB
testcase_23 AC 112 ms
12,900 KB
testcase_24 AC 102 ms
12,964 KB
testcase_25 AC 102 ms
13,136 KB
testcase_26 AC 103 ms
12,760 KB
testcase_27 AC 99 ms
13,056 KB
testcase_28 AC 105 ms
12,916 KB
testcase_29 AC 212 ms
13,076 KB
testcase_30 AC 219 ms
13,024 KB
testcase_31 AC 239 ms
13,172 KB
testcase_32 AC 43 ms
13,136 KB
testcase_33 AC 97 ms
13,104 KB
testcase_34 AC 105 ms
13,056 KB
testcase_35 AC 99 ms
12,996 KB
testcase_36 AC 100 ms
13,084 KB
testcase_37 AC 95 ms
13,140 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub struct SegmentTree<T, M, P> {
    data: Vec<T>,
    n: usize,
    size: usize,
    merge: M,
    propagate: P,
}

impl<T, M, P> SegmentTree<T, M, P>
where
    T: Clone,
    M: Fn(&mut T, &T, &T),
    P: Fn(&mut T, &mut [T]),
{
    pub fn new(a: Vec<T>, merge: M, propagate: P) -> Self {
        let n = a.len();
        assert!(n > 0);
        let size = n.next_power_of_two();
        let mut data = vec![a[0].clone(); 2 * size];
        for (data, ini) in data[size..].iter_mut().zip(a) {
            *data = ini;
        }
        let mut seg = SegmentTree {
            data,
            n,
            size,
            merge,
            propagate,
        };
        for i in (1..size).rev() {
            seg.pull(i);
        }
        seg
    }
    pub fn find<Q>(&mut self, l: usize, r: usize, mut q: Q)
    where
        Q: FnMut(&T),
    {
        assert!(l < r && r <= self.n);
        self.dfs(1, 0, self.size, l, r, false, &mut |t| {
            q(t);
            true
        });
    }
    pub fn update<U>(&mut self, l: usize, r: usize, mut u: U)
    where
        U: FnMut(&mut T),
    {
        assert!(l < r && r <= self.n);
        self.dfs(1, 0, self.size, l, r, true, &mut |t| {
            u(t);
            true
        });
    }
    pub fn update_bool<U>(&mut self, l: usize, r: usize, mut u: U)
    where
        U: FnMut(&mut T) -> bool,
    {
        assert!(l < r && r <= self.n);
        self.dfs(1, 0, self.size, l, r, true, &mut u);
    }
    fn dfs<U>(&mut self, v: usize, l: usize, r: usize, x: usize, y: usize, update: bool, op: &mut U)
    where
        U: FnMut(&mut T) -> bool,
    {
        if x <= l && r <= y && (*op)(&mut self.data[v]) {
            return;
        }
        if r <= self.n {
            self.push(v);
        }
        let mid = (l + r) / 2;
        if x < mid {
            self.dfs(2 * v, l, mid, x, y, update, op);
        }
        if mid < y {
            self.dfs(2 * v + 1, mid, r, x, y, update, op);
        }
        if r <= self.n && update {
            self.pull(v);
        }
    }
    fn pull(&mut self, v: usize) {
        let (f, t) = self.data.split_at_mut(2 * v);
        (self.merge)(&mut f[v], &t[0], &t[1]);
    }
    fn push(&mut self, v: usize) {
        let (f, t) = self.data.split_at_mut(2 * v);
        (self.propagate)(&mut f[v], &mut t[..2]);
    }
}

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

// ---------- 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 ----------

const UPPER: u64 = 1_000_000_000 + 1;

#[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) {
        let g = binary_gcd(x, self.max);
        self.assign(g);
    }
}

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 merge = |x: &mut Node, l: &Node, r: &Node| {
        x.sum = l.sum + r.sum;
        x.max = l.max.max(r.max);
        x.len = l.len + r.len;
        x.lcm = UPPER.min(l.lcm * r.lcm / binary_gcd(l.lcm, r.lcm));
    };
    let propagate = |p: &mut Node, c: &mut [Node]| {
        if p.sum == p.max * p.len {
            for c in c.iter_mut() {
                c.assign(p.max);
            }
        }
    };
    let mut seg = SegmentTree::new(ini, merge, propagate);
    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| {
                if x % node.lcm == 0 {
                    return true;
                }
                node.max * node.len == node.sum && {
                    node.chgcd(x);
                    true
                }
            });
        } else if op == 3 {
            let mut ans = 0;
            seg.find(l, r, |node| ans = ans.max(node.max));
            writeln!(out, "{}", ans).ok();
        } else {
            let mut ans = 0;
            seg.find(l, r, |node| ans += node.sum);
            writeln!(out, "{}", ans).ok();
        }
    }
}
0