#376831 (Rust) No.879 Range Mod 2 Query

• 問題: No.879 Range Mod 2 Query
• ユーザー: niuez
• 提出日時: 2019-09-06 23:19:45
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 266 ms / 3,000 ms
• コード長: 5,900 bytes
• コンパイル時間: 11,647 ms
• コンパイル使用メモリ: 399,228 KB
• 実行使用メモリ: 18,964 KB
• 最終ジャッジ日時: 2024-06-24 22:24:26
• 合計ジャッジ時間: 15,279 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 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	1 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	259 ms; 18,432 KB
testcase_12	AC	150 ms; 17,636 KB
testcase_13	AC	191 ms; 17,888 KB
testcase_14	AC	167 ms; 18,196 KB
testcase_15	AC	178 ms; 11,392 KB
testcase_16	AC	246 ms; 18,944 KB
testcase_17	AC	256 ms; 18,964 KB
testcase_18	AC	266 ms; 18,944 KB
testcase_19	AC	229 ms; 18,920 KB
testcase_20	AC	237 ms; 18,908 KB
testcase_21	AC	251 ms; 18,884 KB

ソースコード

pub trait Magma: Sized + Clone {
  fn op(&self, rhs: &Self) -> Self;
}

pub trait Associative: Magma {}

pub trait Unital: Magma {
  fn identity() -> Self;
}

pub trait Monoid: Magma + Associative + Unital {}

impl<T: Magma + Associative + Unital> Monoid for T {}

pub trait Effector: Monoid {
    type Target;
    fn effect(&self, t: &Self::Target, sz: usize) -> Self::Target;
}


pub struct LazySegmentTree<T: Monoid, E: Effector<Target=T>> {
    node: Vec<T>,
    lazy: Vec<E>,
    sz: usize,
}

impl<T: Monoid, E: Effector<Target=T>> LazySegmentTree<T, E> {
    pub fn init(vec: Vec<T>) -> Self {
        let mut sz = 1;
        while sz < vec.len() { sz *= 2 }
        let mut node = vec![T::identity(); sz << 1];
        let lazy = vec![E::identity(); sz << 1];
        for i in 0..vec.len() { node[i + sz] = vec[i].clone(); }
        for i in (1..sz).rev() { node[i] = node[i << 1].op(&node[(i << 1) + 1]); }
        Self { node: node, lazy: lazy, sz: sz }
    }

    fn push(&mut self, i: usize, sz: usize) {
        self.node[i] = self.lazy[i].effect(&self.node[i], sz);
        if (i << 1) < self.node.len() {
            self.lazy[i << 1] = self.lazy[i << 1].op(&self.lazy[i]);
            self.lazy[(i << 1) + 1] = self.lazy[(i << 1) + 1].op(&self.lazy[i]);
        }
        self.lazy[i] = E::identity();
    }

    fn update_raw(&mut self, i: usize, a: usize, b: usize, l: usize, r: usize, e: &E) {
        self.push(i, r - l);
        if b <= l || r <= a { return; }
        else if a <= l && r <= b {
            self.lazy[i] = self.lazy[i].op(e);
            self.push(i, r - l);
        }
        else {
            self.update_raw(i << 1, a, b, l, (l + r) >> 1, e);
            self.update_raw((i << 1) + 1, a, b, (l + r) >> 1, r, e);
            self.node[i] = self.node[i << 1].op(&self.node[(i << 1) + 1]);
        }
    }

    pub fn update_range(&mut self, l: usize, r: usize, e: E) {
        let sz = self.sz;
        self.update_raw(1, l, r, 0, sz, &e);
    }

    fn fold_raw(&mut self, i: usize, a: usize, b: usize, l: usize, r: usize) -> T {
        self.push(i, r - l);
        if b <= l || r <= a { T::identity() }
        else if a <= l && r <= b { self.node[i].clone() }
        else {
            self.fold_raw(i << 1, a, b, l, (l + r) >> 1)
                .op(&self.fold_raw((i << 1) + 1, a, b, (l + r) >> 1, r))
        }
    }

    pub fn fold(&mut self, l: usize, r: usize) -> T {
        let sz = self.sz;
        self.fold_raw(1, l, r, 0, sz)
    }
}

#[derive(Clone)]
struct Am {
    sum: usize,
    even: usize,
    odd: usize,
}

impl Magma for Am {
    fn op(&self, right: &Self) -> Self { Am {
        sum: self.sum + right.sum,
        even: self.even + right.even,
        odd: self.odd + right.odd,
    }}
}
impl Associative for Am {}

impl Unital for Am {
    fn identity() -> Self { Am {
        sum: 0,
        even: 0,
        odd: 0,
    }}
}


#[derive(Clone)]
enum Uq {
    Plus(usize),
    Update(usize, usize),
}

impl Magma for Uq {
    fn op(&self, right: &Self) -> Self {
        match self.clone() {
            Uq::Plus(x) => {
                match right.clone() {
                    Uq::Plus(y) => Uq::Plus(x + y),
                    Uq::Update(even, odd) => {
                        if x % 2 == 0 { Uq::Update(even, odd) }
                        else { Uq::Update(odd, even) }
                    }
                }
            }
            Uq::Update(e, o) => {
                match right.clone() {
                    Uq::Plus(y) => Uq::Update(e + y, o + y),
                    Uq::Update(even, odd) => {
                        if e % 2 == 0 { Uq::Update(even, odd) }
                        else { Uq::Update(odd, even) }
                    }
                }
            }
        }
    }
}
impl Associative for Uq {}
impl Unital for Uq {
    fn identity() -> Self { Uq::Plus(0) }
}
impl Effector for Uq {
    type Target = Am;
    fn effect(&self, t: &Self::Target, len : usize) -> Self::Target {
        match self.clone() {
            Uq::Plus(x) => {
                if x % 2 == 0 {
                    Am {
                        sum: t.sum + len * x,
                        even: t.even,
                        odd: t.odd,
                    }
                }
                else {
                    Am {
                        sum: t.sum + len * x,
                        even: t.odd,
                        odd: t.even,
                    }
                }
            }
            Uq::Update(even, odd) => {
                Am {
                    sum: t.even * even + t.odd * odd,
                    even: if even % 2 == 0 { t.even } else { t.odd },
                    odd: if even % 2 == 0 { t.odd } else { t.even },
                }
            }
        }
    }
}

use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let q: usize = iter.next().unwrap().parse().unwrap();
    let mut vec = Vec::new();
    for _ in 0..n {
        let a: usize = iter.next().unwrap().parse().unwrap();
        if a % 2 == 0 { vec.push(Am { sum: a, even: 1, odd: 0 }); }
        else { vec.push(Am { sum: a, even: 0, odd: 1 }); }
    }
    let mut seg = LazySegmentTree::<Am, Uq>::init(vec);
    for _ in 0..q {
        let com: usize = iter.next().unwrap().parse().unwrap();
        let l: usize = iter.next().unwrap().parse().unwrap();
        let r: usize = iter.next().unwrap().parse().unwrap();
        if com == 1 {
            seg.update_range(l - 1, r, Uq::Update(0, 1));
        }
        else if com == 2 {
            let x: usize = iter.next().unwrap().parse().unwrap();
            seg.update_range(l - 1, r, Uq::Plus(x));
        }
        else {
            println!("{}", seg.fold(l - 1, r).sum);
        }
    }
}