結果

問題 No.879 Range Mod 2 Query
ユーザー niuezniuez
提出日時 2019-09-06 23:19:45
言語 Rust
(1.77.0)
結果
AC  
実行時間 288 ms / 3,000 ms
コード長 5,900 bytes
コンパイル時間 5,535 ms
コンパイル使用メモリ 148,448 KB
実行使用メモリ 20,668 KB
最終ジャッジ日時 2023-09-07 03:47:38
合計ジャッジ時間 8,351 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 279 ms
20,136 KB
testcase_12 AC 157 ms
18,004 KB
testcase_13 AC 202 ms
18,068 KB
testcase_14 AC 176 ms
18,324 KB
testcase_15 AC 179 ms
11,704 KB
testcase_16 AC 262 ms
20,588 KB
testcase_17 AC 277 ms
20,668 KB
testcase_18 AC 288 ms
20,652 KB
testcase_19 AC 250 ms
20,624 KB
testcase_20 AC 248 ms
20,648 KB
testcase_21 AC 268 ms
20,652 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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