結果

問題 No.1099 Range Square Sum
ユーザー akakimidoriakakimidori
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// ---------- 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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0