結果
問題 | No.749 クエリ全部盛り |
ユーザー |
![]() |
提出日時 | 2019-09-07 12:36:45 |
言語 | Rust (1.77.0 + proconio) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,210 bytes |
コンパイル時間 | 12,432 ms |
コンパイル使用メモリ | 387,464 KB |
最終ジャッジ日時 | 2024-11-14 21:38:22 |
合計ジャッジ時間 | 13,297 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `,` --> src/main.rs:5:20 | 5 | fn fold(Self::T, Self::T) -> Self::T; | ^ expected one of 9 possible tokens | = note: anonymous parameters are removed in the 2018 edition (see RFC 1685) help: explicitly ignore the parameter name | 5 | fn fold(_: Self::T, Self::T) -> Self::T; | ~~~~~~~~~~ error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `)` --> src/main.rs:5:29 | 5 | fn fold(Self::T, Self::T) -> Self::T; | ^ expected one of 9 possible tokens | = note: anonymous parameters are removed in the 2018 edition (see RFC 1685) help: explicitly ignore the parameter name | 5 | fn fold(Self::T, _: Self::T) -> Self::T; | ~~~~~~~~~~ error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `,` --> src/main.rs:6:20 | 6 | fn eval(Self::T, Self::E) -> Self::T; | ^ expected one of 9 possible tokens | = note: anonymous parameters are removed in the 2018 edition (see RFC 1685) help: explicitly ignore the parameter name | 6 | fn eval(_: Self::T, Self::E) -> Self::T; | ~~~~~~~~~~ error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `)` --> src/main.rs:6:29 | 6 | fn eval(Self::T, Self::E) -> Self::T; | ^ expected one of 9 possible tokens | = note: anonymous parameters are removed in the 2018 edition (see RFC 1685) help: explicitly ignore the parameter name | 6 | fn eval(Self::T, _: Self::E) -> Self::T; | ~~~~~~~~~~ error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `,` --> src/main.rs:7:21 | 7 | fn merge(Self::E, Self::E) -> Self::E; | ^ expected one of 9 possible tokens | = note: anonymous parameters are removed i
ソースコード
// ---------- begin Lazy Segment Tree ---------- pub trait TE { type T: Clone; type E: Clone; fn fold(Self::T, Self::T) -> Self::T; fn eval(Self::T, Self::E) -> Self::T; fn merge(Self::E, Self::E) -> Self::E; fn e() -> Self::T; fn id() -> Self::E; } pub struct LazySegmentTree<R: TE> { size: usize, bit: usize, a: Vec<(R::T, R::E)>, } impl <R: TE> LazySegmentTree<R> { pub fn new(n: usize) -> LazySegmentTree<R> { let mut bit = 0; while (1 << bit) < n { bit += 1; } LazySegmentTree { size: 1 << bit, bit: bit, a: vec![(R::e(), R::id()); 2 << bit], } } pub fn build_by(z: &[R::T]) -> LazySegmentTree<R> { let n = z.len(); let mut bit = 0; while (1 << bit) < n { bit += 1; } let mut a = vec![(R::e(), R::id()); 2 << bit]; for (a, z) in a[(1 << bit)..].iter_mut().zip(z.iter()) { a.0 = z.clone(); } for i in (1..(1 << bit)).rev() { let l = R::eval(a[2 * i].0.clone(), a[2 * i].1.clone()); let r = R::eval(a[2 * i + 1].0.clone(), a[2 * i + 1].1.clone()); a[i].0 = R::fold(l, r); } LazySegmentTree { size: 1 << bit, bit : bit, a: a, } } fn eval(&self, k: usize) -> R::T { R::eval(self.a[k].0.clone(), self.a[k].1.clone()) } fn propagate(&mut self, x: usize) { let x = x + self.size; for i in (1..(self.bit + 1)).rev() { let k = x >> i; self.a[2 * k].1 = R::merge(self.a[2 * k].1.clone(), self.a[k].1.clone()); self.a[2 * k + 1].1 = R::merge(self.a[2 * k + 1].1.clone(), self.a[k].1.clone()); self.a[k].1 = R::id(); self.a[k].0 = R::fold(self.eval(2 * k), self.eval(2 * k + 1)); } } fn save(&mut self, x: usize) { let x = x + self.size; for i in 1..(self.bit + 1) { let k = x >> i; self.a[k].0 = R::fold(self.eval(2 * k), self.eval(2 * k + 1)); } } pub fn update(&mut self, l: usize, r: usize, op: R::E) { self.propagate(l); self.propagate(r - 1); let mut x = l + self.size; let mut y = r + self.size; while x < y { if x & 1 == 1 { self.a[x].1 = R::merge(self.a[x].1.clone(), op.clone()); x += 1; } if y & 1 == 1 { y -= 1; self.a[y].1 = R::merge(self.a[y].1.clone(), op.clone()); } x >>= 1; y >>= 1; } self.save(l); self.save(r - 1); } pub fn find(&mut self, l: usize, r: usize) -> R::T { self.propagate(l); self.propagate(r - 1); let mut x = l + self.size; let mut y = r + self.size; let mut p = R::e(); let mut q = R::e(); while x < y { if x & 1 == 1 { p = R::fold(p, self.eval(x)); x += 1; } if y & 1 == 1 { y -= 1; q = R::fold(self.eval(y), q); } x >>= 1; y >>= 1; } R::fold(p, q) } } // ---------- end Lazy Segment Tree ---------- const MOD: u64 = 1_000_000_007; fn add(a: u64, b: u64) -> u64 { let d = a + b; if d >= MOD {d - MOD} else {d} } struct R; impl TE for R { type T = (u64, u64, u64); type E = (u64, u64, u64); fn fold(l: Self::T, r: Self::T) -> Self::T { (add(l.0, r.0), l.1 + r.1, add(l.2, r.2)) } fn eval(a: Self::T, f: Self::E) -> Self::T { ((a.0 * f.0 + f.1 * a.1 + f.2 * a.2) % MOD, a.1, a.2) } fn merge(f: Self::E, g: Self::E) -> Self::E { (f.0 * g.0 % MOD, (f.1 * g.0 + g.1) % MOD, (f.2 * g.0 + g.2) % MOD) } fn e() -> Self::T { (0, 0, 0) } fn id() -> Self::E { (1, 0, 0) } } use std::io::{Read, Write}; fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let q: usize = it.next().unwrap().parse().unwrap(); let mut z = vec![(0, 1, 0); n + 1]; z[1].2 = 1; for i in 2..n { z[i].2 = add(z[i - 1].2 , z[i - 2].2); } let mut s = LazySegmentTree::<R>::build_by(&z); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); for _ in 0..q { let q: u8 = it.next().unwrap().parse().unwrap(); let l: usize = it.next().unwrap().parse().unwrap(); let r: usize = it.next().unwrap().parse().unwrap(); let k: u64 = it.next().unwrap().parse().unwrap(); match q { 0 => { let ans = s.find(l, r + 1).0 * k % MOD; writeln!(out, "{}", ans).unwrap(); }, 1 => s.update(l, r + 1, (0, k, 0)), 2 => s.update(l, r + 1, (1, k, 0)), 3 => s.update(l, r + 1, (k, 0, 0)), _ => s.update(l, r + 1, (1, 0, k)), } } } fn main() { run(); }