結果
問題 | No.1099 Range Square Sum |
ユーザー | koba-e964 |
提出日時 | 2020-06-26 21:55:52 |
言語 | Rust (1.77.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,424 bytes |
コンパイル時間 | 15,754 ms |
コンパイル使用メモリ | 379,708 KB |
実行使用メモリ | 19,328 KB |
最終ジャッジ日時 | 2024-07-04 20:59:17 |
合計ジャッジ時間 | 16,861 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
ソースコード
#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::{Read, Write, BufWriter}; #[allow(unused)] macro_rules! debug { ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap()); } #[allow(unused)] macro_rules! debugln { ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap()); } fn get_word() -> String { let stdin = std::io::stdin(); let mut stdin=stdin.lock(); let mut u8b: [u8; 1] = [0]; loop { let mut buf: Vec<u8> = Vec::with_capacity(16); loop { let res = stdin.read(&mut u8b); if res.unwrap_or(0) == 0 || u8b[0] <= b' ' { break; } else { buf.push(u8b[0]); } } if buf.len() >= 1 { let ret = String::from_utf8(buf).unwrap(); return ret; } } } #[allow(dead_code)] fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() } /** * Lazy Segment Tree. This data structure is useful for fast folding and updating on intervals of an array * whose elements are elements of monoid T. Note that constructing this tree requires the identity * element of T and the operation of T. This is monomorphised, because of efficiency. T := i64, biop = max, upop = (+) * Reference: http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261 * Verified by https://codeforces.com/contest/1114/submission/49759034 */ pub trait ActionRing { type T: Clone + Copy; // data type U: Clone + Copy + PartialEq + Eq; // action fn biop(x: Self::T, y: Self::T) -> Self::T; fn update(x: Self::T, a: Self::U, height: usize) -> Self::T; fn upop(fst: Self::U, snd: Self::U) -> Self::U; fn e() -> Self::T; fn upe() -> Self::U; // identity for upop } pub struct LazySegTree<R: ActionRing> { n: usize, dep: usize, dat: Vec<R::T>, lazy: Vec<R::U>, } impl<R: ActionRing> LazySegTree<R> { pub fn new(n_: usize) -> Self { let mut n = 1; let mut dep = 0; while n < n_ { n *= 2; dep += 1; } // n is a power of 2 LazySegTree { n: n, dep: dep, dat: vec![R::e(); 2 * n - 1], lazy: vec![R::upe(); 2 * n - 1] } } #[inline] fn lazy_evaluate_node(&mut self, k: usize, height: usize) { if self.lazy[k] == R::upe() { return; } self.dat[k] = R::update(self.dat[k], self.lazy[k], height); if k < self.n - 1 { self.lazy[2 * k + 1] = R::upop(self.lazy[2 * k + 1], self.lazy[k]); self.lazy[2 * k + 2] = R::upop(self.lazy[2 * k + 2], self.lazy[k]); } self.lazy[k] = R::upe(); // identity for upop } #[inline] fn update_node(&mut self, k: usize) { self.dat[k] = R::biop(self.dat[2 * k + 1], self.dat[2 * k + 2]); } fn update_sub(&mut self, a: usize, b: usize, v: R::U, k: usize, height: usize, l: usize, r: usize) { self.lazy_evaluate_node(k, height); // [a,b) and [l,r) intersects? if r <= a || b <= l {return;} if a <= l && r <= b { self.lazy[k] = R::upop(self.lazy[k], v); self.lazy_evaluate_node(k, height); return; } self.update_sub(a, b, v, 2 * k + 1, height - 1, l, (l + r) / 2); self.update_sub(a, b, v, 2 * k + 2, height - 1, (l + r) / 2, r); self.update_node(k); } /* ary[i] = upop(ary[i], v) for i in [a, b) (half-inclusive) */ #[inline] pub fn update(&mut self, a: usize, b: usize, v: R::U) { let n = self.n; let dep = self.dep; self.update_sub(a, b, v, 0, dep, 0, n); } /* l,r are for simplicity */ fn query_sub(&mut self, a: usize, b: usize, k: usize, height: usize, l: usize, r: usize) -> R::T { self.lazy_evaluate_node(k, height); // [a,b) and [l,r) intersect? if r <= a || b <= l {return R::e();} if a <= l && r <= b {return self.dat[k];} let vl = self.query_sub(a, b, 2 * k + 1, height - 1, l, (l + r) / 2); let vr = self.query_sub(a, b, 2 * k + 2, height - 1, (l + r) / 2, r); self.update_node(k); R::biop(vl, vr) } /* [a, b) (note: half-inclusive) */ #[inline] pub fn query(&mut self, a: usize, b: usize) -> R::T { let n = self.n; let dep = self.dep; self.query_sub(a, b, 0, dep, 0, n) } } enum Affine {} impl ActionRing for Affine { type T = [i64; 3]; // data type U = (i64, i64); // action, x |-> (1 a a^2) |-> (1 a+x (a+x)^2) fn biop(x: Self::T, y: Self::T) -> Self::T { let mut z = [0; 3]; for i in 0..3 { z[i] = x[i] + y[i]; } z } fn update(a: Self::T, add: Self::U, height: usize) -> Self::T { let (init, add) = add; if init == 1 { return [1, add, add * add]; } let add = add << height; let mut z = a; z[1] += a[0] * add; z[2] += a[0] * add * add; z[2] += a[1] * 2 * add; z } fn upop(fst: Self::U, snd: Self::U) -> Self::U { if fst.0 == 0 && snd.0 == 0 { (0, fst.1 + snd.1) } else if snd.0 == 1 { snd } else { (1, fst.1 + snd.1) } } fn e() -> Self::T { [0, 0, 0] } fn upe() -> Self::U { // identity for upop (0, 0) } } fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($($format:tt)*) => (let _ = write!(out,$($format)*);); } let n: usize = get(); let a: Vec<i64> = (0..n).map(|_| get()).collect(); let mut st = LazySegTree::<Affine>::new(n); st.update(0, n, (1, 0)); for i in 0..n { st.update(i, i + 1, (0, a[i])); } let q: usize = get(); for _ in 0..q { let ty: i32 = get(); let l = get::<usize>() - 1; let r = get::<usize>(); if ty == 1 { let x: i64 = get(); st.update(l, r, (0, x)); } else { let z = st.query(l, r); puts!("{}\n", z[2]); } } } fn main() { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 104_857_600; // 100 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); }