結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-26 21:42:55 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 5,286 bytes |
コンパイル時間 | 13,130 ms |
コンパイル使用メモリ | 382,780 KB |
実行使用メモリ | 24,320 KB |
最終ジャッジ日時 | 2024-07-04 20:23:55 |
合計ジャッジ時間 | 15,547 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
// ---------- begin Lazy Segment Tree ----------pub trait TE {type T: Clone;type E: Clone;fn fold(l: &Self::T, r: &Self::T) -> Self::T;fn eval(x: &Self::T, f: &Self::E) -> Self::T;fn merge(g: &Self::E, h: &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 size = n.next_power_of_two();let bit = size.trailing_zeros() as usize;LazySegmentTree {size: size,bit: bit,a: vec![(R::e(), R::id()); 2 * size],}}pub fn build_by(z: &[R::T]) -> LazySegmentTree<R> {let mut seg = LazySegmentTree::<R>::new(z.len());for (a, z) in seg.a[seg.size..].iter_mut().zip(z.iter()) {a.0 = z.clone();}let a = &mut seg.a;for i in (1..seg.size).rev() {a[i].0 = R::fold(&a[2 * i].0, &a[2 * i + 1].0);}seg}fn apply(&mut self, x: usize, op: &R::E) {let node = &mut self.a[x];node.0 = R::eval(&node.0, op);node.1 = R::merge(&node.1, op);}fn propagate(&mut self, x: usize) {let mut op = R::id();std::mem::swap(&mut op, &mut self.a[x].1);self.apply(2 * x, &op);self.apply(2 * x + 1, &op);}fn propagate_range(&mut self, l: usize, r: usize) {let x = l + self.size;let y = r + self.size;let mut k = self.bit;while (x >> k) == (y >> k) {self.propagate(x >> k);k -= 1;}for i in ((x.trailing_zeros() as usize + 1)..=k).rev() {self.propagate(x >> i);}for i in ((y.trailing_zeros() as usize + 1)..=k).rev() {self.propagate(y >> i);}}fn save_range(&mut self, l: usize, r: usize) {let mut x = l + self.size;let mut y = r + self.size;let mut p = (x & 1) == 1;let mut q = (y & 1) == 1;x >>= 1;y >>= 1;while 0 < x && x < y {if p {self.a[x].0 = R::fold(&self.a[2 * x].0, &self.a[2 * x + 1].0);}if q {self.a[y].0 = R::fold(&self.a[2 * y].0, &self.a[2 * y + 1].0);}p |= (x & 1) == 1;q |= (y & 1) == 1;x >>= 1;y >>= 1;}while 0 < x {self.a[x].0 = R::fold(&self.a[2 * x].0, &self.a[2 * x + 1].0);x >>= 1;}}pub fn update(&mut self, l: usize, r: usize, op: R::E) {self.propagate_range(l, r);let mut x = l + self.size;let mut y = r + self.size;while x < y {if x & 1 == 1 {self.apply(x, &op);x += 1;}if y & 1 == 1 {y -= 1;self.apply(y, &op);}x >>= 1;y >>= 1;}self.save_range(l, r);}pub fn find(&mut self, l: usize, r: usize) -> R::T {self.propagate_range(l, r);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.a[x].0);x += 1;}if y & 1 == 1 {y -= 1;q = R::fold(&self.a[y].0, &q);}x >>= 1;y >>= 1;}R::fold(&p, &q)}}// ---------- end Lazy Segment Tree ----------use std::io::Read;use std::io::Write;struct R;impl TE for R {type T = (i64, i64, i64);type E = i64;fn fold(l: &Self::T, r: &Self::T) -> Self::T {(l.0 + r.0, l.1 + r.1, l.2 + r.2)}fn eval(x: &Self::T, f: &Self::E) -> Self::T {let y = x.1 + x.0 * *f;let z = x.2 + 2 * *f * x.1 + *f * *f * x.0;(x.0, y, z)}fn merge(g: &Self::E, h: &Self::E) -> Self::E {*g + *h}fn e() -> Self::T {(0, 0, 0)}fn id() -> Self::E {0}}fn run() {let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());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 mut a = vec![];for _ in 0..n {let v: i64 = it.next().unwrap().parse().unwrap();a.push((1, v, v * v));}let mut seg = LazySegmentTree::<R>::build_by(&a);let q = it.next().unwrap().parse::<usize>().unwrap();for _ in 0..q {let op = it.next().unwrap().parse::<usize>().unwrap();let l = it.next().unwrap().parse::<usize>().unwrap() - 1;let r = it.next().unwrap().parse::<usize>().unwrap();if op == 1 {let x = it.next().unwrap().parse::<i64>().unwrap();seg.update(l, r, x);} else {let ans = seg.find(l, r).2;writeln!(out, "{}", ans).ok();}}}fn main() {run();}