use proconio::{input, marker::Usize1}; fn main() { input!{ n: usize, m: usize, mut alr: [(i64, Usize1, Usize1); n], q: usize, xyuv: [(Usize1, Usize1, Usize1, Usize1); q], } let mut seg = DynamicSegtree::::new(0, m + 2); let mut seg2 = DynamicSegtree::::new(0, m + 2); let mut ans: i64 = 0; for i in 0..n{ seg2.set(i, alr[i].0); seg.set(alr[i].1, seg.prod(alr[i].1, alr[i].1 + 1) + 1); seg.set(alr[i].2 + 1, seg.prod(alr[i].2 + 1, alr[i].2 + 2) - 1); ans += alr[i].0 * (alr[i].2 - alr[i].1 + 1) as i64 } for i in 0..n{ ans -= seg.prod(0, i + 1) * alr[i].0; } let mut idx = (0..n).collect::>(); for (x, y, u, v) in xyuv{ ans += seg.prod(0, idx[x] + 1) * alr[x].0; seg.set(alr[x].1, seg.prod(alr[x].1, alr[x].1 + 1) - 1); seg.set(alr[x].2 + 1, seg.prod(alr[x].2 + 1, alr[x].2 + 2) + 1); seg2.set(idx[x], 0); ans += seg2.prod(alr[x].1, alr[x].2 + 1); ans -= alr[x].0 * (alr[x].2 - alr[x].1 + 1) as i64; idx[x] = y; (alr[x].1, alr[x].2) = (u, v); ans += alr[x].0 * (alr[x].2 - alr[x].1 + 1) as i64; ans -= seg2.prod(alr[x].1, alr[x].2 + 1); seg2.set(idx[x], alr[x].0); seg.set(alr[x].1, seg.prod(alr[x].1, alr[x].1 + 1) + 1); seg.set(alr[x].2 + 1, seg.prod(alr[x].2 + 1, alr[x].2 + 2) - 1); ans -= seg.prod(0, idx[x] + 1) * alr[x].0; println!("{}", ans); } } struct M; impl Monoid for M { type S = i64; fn identity() -> Self::S { 0 } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { a + b } } trait Monoid { type S: Clone; fn identity() -> Self::S; fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S; } struct DynamicSegtree { l: usize, r: usize, value: M::S, left: Option>>, right: Option>>, } impl DynamicSegtree { fn new(l: usize, r: usize) -> Self { Self { l, r, value: M::identity(), left: None, right: None, } } fn update(&mut self, idx: usize, val: M::S) { if idx < self.l || idx >= self.r { return; } if self.r - self.l == 1 { self.value = M::binary_operation(&self.value.clone(), &val); return; } let mid = (self.l + self.r) / 2; if idx < mid { if self.left.is_none() { self.left = Some(Box::new(DynamicSegtree::::new(self.l, mid))); } self.left.as_mut().unwrap().update(idx, val.clone()); } else { if self.right.is_none() { self.right = Some(Box::new(DynamicSegtree::::new(mid, self.r))); } self.right.as_mut().unwrap().update(idx, val.clone()); } let left_val = self.left.as_ref().map(|node| node.value.clone()).unwrap_or(M::identity()); let right_val = self.right.as_ref().map(|node| node.value.clone()).unwrap_or(M::identity()); self.value = M::binary_operation(&left_val, &right_val); } fn set(&mut self, idx: usize, val: M::S) { if idx < self.l || idx >= self.r { return; } if self.r - self.l == 1 { self.value = val; return; } let mid = (self.l + self.r) / 2; if idx < mid { if self.left.is_none() { self.left = Some(Box::new(DynamicSegtree::::new(self.l, mid))); } self.left.as_mut().unwrap().set(idx, val.clone()); } else { if self.right.is_none() { self.right = Some(Box::new(DynamicSegtree::::new(mid, self.r))); } self.right.as_mut().unwrap().set(idx, val.clone()); } let left_val = self.left.as_ref().map(|node| node.value.clone()).unwrap_or(M::identity()); let right_val = self.right.as_ref().map(|node| node.value.clone()).unwrap_or(M::identity()); self.value = M::binary_operation(&left_val, &right_val); } fn prod(&self, ql: usize, qr: usize) -> M::S { if self.r <= ql || qr <= self.l { return M::identity(); } if ql <= self.l && self.r <= qr { return self.value.clone(); } let left_res = self.left.as_ref().map(|node| node.prod(ql, qr)).unwrap_or(M::identity()); let right_res = self.right.as_ref().map(|node| node.prod(ql, qr)).unwrap_or(M::identity()); M::binary_operation(&left_res, &right_res) } }