結果

問題 No.879 Range Mod 2 Query
ユーザー akakimidoriakakimidori
提出日時 2019-09-07 03:41:37
言語 Rust
(1.77.0)
結果
AC  
実行時間 242 ms / 3,000 ms
コード長 6,706 bytes
コンパイル時間 4,340 ms
コンパイル使用メモリ 153,612 KB
実行使用メモリ 21,096 KB
最終ジャッジ日時 2023-09-07 09:01:53
合計ジャッジ時間 8,478 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,384 KB
testcase_11 AC 223 ms
18,380 KB
testcase_12 AC 155 ms
16,784 KB
testcase_13 AC 178 ms
16,768 KB
testcase_14 AC 174 ms
17,900 KB
testcase_15 AC 155 ms
12,168 KB
testcase_16 AC 230 ms
19,864 KB
testcase_17 AC 238 ms
20,012 KB
testcase_18 AC 242 ms
19,832 KB
testcase_19 AC 183 ms
20,264 KB
testcase_20 AC 184 ms
21,096 KB
testcase_21 AC 190 ms
21,076 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ---------- begin Lazy Segment Tree ----------
mod segment_tree {
    pub struct Lazy<T, E, F, G, H> {
        n: usize,
        k: usize,
        a: Vec<(T, E)>,
        e: T,
        id: E,
        f: F,
        g: G,
        h: H,
    }
    #[allow(dead_code)]
    impl<T: Clone, E: Clone, F: Fn(T, T) -> T, G: Fn(T, E) -> T, H: Fn(E, E) -> E> Lazy<T, E, F, G, H> {
        pub fn new(n: usize, e: T, id: E, f: F, g: G, h: H) -> Lazy<T, E, F, G, H> {
            let mut k = 0;
            while (1 << k) < n {
                k += 1;
            }
            Lazy {
                n: 1 << k,
                k: k,
                a: vec![(e.clone(), id.clone()); 2 << k],
                e: e,
                id: id,
                f: f,
                g: g,
                h: h,
            }
        }
        pub fn build_by(z: &Vec<T>, e: T, id: E, f: F, g: G, h: H) -> Lazy<T, E, F, G, H> {
            let n = z.len();
            let mut k = 0;
            while (1 << k) < n {
                k += 1;
            }
            let mut a = vec![(e.clone(), id.clone()); 2 << k];
            for i in 0..n {
                a[(1 << k) + i].0 = z[i].clone();
            }
            for i in (1..(1 << k)).rev() {
                let l = g(a[2 * i].0.clone(), id.clone());
                let r = g(a[2 * i + 1].0.clone(), id.clone());
                a[i].0 = f(l, r);
            }
            Lazy {
                n: 1 << k,
                k: k,
                a: a,
                e: e,
                id: id,
                f: f,
                g: g,
                h: h,
            }
        }
        fn eval (&self, x: usize) -> T {
            (self.g)(self.a[x].0.clone(), self.a[x].1.clone())
        }
        fn propagate (&mut self, mut x: usize) {
            x += self.n;
            for k in (1..(self.k + 1)).rev() {
                let y = x >> k;
                self.a[2 * y].1 = (self.h)(self.a[2 * y].1.clone(), self.a[y].1.clone());
                self.a[2 * y + 1].1 = (self.h)(self.a[2 * y + 1].1.clone(), self.a[y].1.clone());
                self.a[y].1 = self.id.clone();
                self.a[y].0 = (self.f)(self.eval(2 * y), self.eval(2 * y + 1));
            }
        }
        fn save (&mut self, x: usize) {
            let mut k = (x + self.n) >> 1;
            while k > 0 {
                self.a[k].0 = (self.f)(self.eval(2 * k), self.eval(2 * k + 1));
                k >>= 1;
            }
        }
        pub fn update (&mut self, l: usize, r: usize, p: E) {
            self.propagate(l);
            self.propagate(r - 1);
            let mut x = l + self.n;
            let mut y = r + self.n;
            while x < y {
                if (x & 1) == 1 {
                    self.a[x].1 = (self.h)(self.a[x].1.clone(), p.clone());
                    x += 1;
                }
                if (y & 1) == 1 {
                    y -= 1;
                    self.a[y].1 = (self.h)(self.a[y].1.clone(), p.clone());
                }
                x >>= 1;
                y >>= 1;
            }
            self.save(l);
            self.save(r - 1);
        }
        pub fn find (&mut self, l: usize, r: usize) -> T {
            self.propagate(l);
            self.propagate(r - 1);
            let mut p = self.e.clone();
            let mut q = self.e.clone();
            let mut x = l + self.n;
            let mut y = r + self.n;
            while x < y {
                if (x & 1) == 1 {
                    p = (self.f)(p, self.eval(x));
                    x += 1;
                }
                if (y & 1) == 1 {
                    y -= 1;
                    q = (self.f)(self.eval(y), q);
                }
                x >>= 1;
                y >>= 1;
            }
            (self.f)(p, q)
        }
    }
}
// ---------- end Lazy Segment Tree ----------
//---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    use std::str::SplitWhitespace;
    use std::io::Read;
    use std;
    pub struct Scanner<'a> {
        it: SplitWhitespace<'a>
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace()
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            match self.it.next().unwrap().parse::<T>() {
                Ok(v) => v,
                _ => panic!("Scanner error")
            }
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.next::<String>().chars().collect()
        }
    }
    pub fn read_string() -> String {
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }
}
//---------- end scannner ----------

use std::io::Write;

fn main() {
    let sc = scanner::read_string();
    let sc = scanner::Scanner::new(&sc);
    let out = std::io::stdout();
    let out = std::io::BufWriter::new(out.lock());
    run(sc, out);
}

fn run(mut sc: scanner::Scanner, mut out: std::io::BufWriter<std::io::StdoutLock>) {
    let n: usize = sc.next();
    let q: usize = sc.next();
    let a: Vec<u64> = (0..n).map(|_| sc.next()).collect();
    type T = (u64, u64, u64);//和、奇数、偶数
    type E = (u64, bool, u64);//&1後の加算、&1, &1前の加算
    let f = |a: T, b: T| (a.0 + b.0, a.1 + b.1, a.2 + b.2);
    let g = |a: T, b: E| {
        if !b.1 {
            let (odd, even) = if (b.0 + b.2) % 2 == 0 {(a.1, a.2)} else {(a.2, a.1)};
            return (a.0 + (b.0 + b.2) * (a.1 + a.2), odd, even);
        }
        let (x, y) = if b.2 % 2 == 0 {(a.1, a.2)} else {(a.2, a.1)};
        let (odd, even) = if b.0 % 2 == 0 {(x, y)} else {(y, x)};
        (b.0 * (x + y) + x, odd, even)
    };
    let h = |a: E, b: E| {
        if !b.1 {
            return (a.0 + b.0 + b.2, a.1, a.2);
        }
        if !a.1 {
            return (b.0, b.1, b.2 + a.0 + a.2);
        }
        if (a.0 + b.2) % 2 == 0 {
            (b.0, true, a.2)
        } else {
            (b.0, true, a.2 + 1)
        }
    };
    let mut s = segment_tree::Lazy::build_by(&vec![(0, 0, 1); n], (0, 0, 0), (0, false, 0), f, g, h);
    for i in 0..n {
        s.update(i, i + 1, (a[i], false, 0));
    }
    for _ in 0..q {
        let op: u8 = sc.next();
        let l = sc.next::<usize>() - 1;
        let r = sc.next::<usize>();
        match op {
            1 => s.update(l, r, (0, true, 0)),
            2 => {
                let x: u64 = sc.next();
                s.update(l, r, (x, false, 0));
            },
            _ => {
                let ans = s.find(l, r).0;
                writeln!(out, "{}", ans).unwrap();
            },
        }
    }
}
0