/* gptによりpythonからC++に変換 import typing def _ceil_pow2(n: int) -> int: x = 0 while (1 << x) < n: x += 1 return x def _bsf(n: int) -> int: x = 0 while n % 2 == 0: x += 1 n //= 2 return x class LazySegTree: def __init__( self, op: typing.Callable[[typing.Any, typing.Any], typing.Any], e: typing.Any, mapping: typing.Callable[[typing.Any, typing.Any], typing.Any], composition: typing.Callable[[typing.Any, typing.Any], typing.Any], id_: typing.Any, v: typing.Union[int, typing.List[typing.Any]]) -> None: self._op = op self._e = e self._mapping = mapping self._composition = composition self._id = id_ if isinstance(v, int): v = [e] * v self._n = len(v) self._log = _ceil_pow2(self._n) self._size = 1 << self._log self._d = [e] * (2 * self._size) self._lz = [self._id] * self._size for i in range(self._n): self._d[self._size + i] = v[i] for i in range(self._size - 1, 0, -1): self._update(i) def set(self, p: int, x: typing.Any) -> None: assert 0 <= p < self._n p += self._size for i in range(self._log, 0, -1): self._push(p >> i) self._d[p] = x for i in range(1, self._log + 1): self._update(p >> i) def get(self, p: int) -> typing.Any: assert 0 <= p < self._n p += self._size for i in range(self._log, 0, -1): self._push(p >> i) return self._d[p] def prod(self, left: int, right: int) -> typing.Any: assert 0 <= left <= right <= self._n if left == right: return self._e left += self._size right += self._size for i in range(self._log, 0, -1): if ((left >> i) << i) != left: self._push(left >> i) if ((right >> i) << i) != right: self._push((right - 1) >> i) sml = self._e smr = self._e while left < right: if left & 1: sml = self._op(sml, self._d[left]) left += 1 if right & 1: right -= 1 smr = self._op(self._d[right], smr) left >>= 1 right >>= 1 return self._op(sml, smr) def all_prod(self) -> typing.Any: return self._d[1] def apply(self, left: int, right: typing.Optional[int] = None, f: typing.Optional[typing.Any] = None) -> None: assert f is not None if right is None: p = left assert 0 <= left < self._n p += self._size for i in range(self._log, 0, -1): self._push(p >> i) self._d[p] = self._mapping(f, self._d[p]) for i in range(1, self._log + 1): self._update(p >> i) else: assert 0 <= left <= right <= self._n if left == right: return left += self._size right += self._size for i in range(self._log, 0, -1): if ((left >> i) << i) != left: self._push(left >> i) if ((right >> i) << i) != right: self._push((right - 1) >> i) l2 = left r2 = right while left < right: if left & 1: self._all_apply(left, f) left += 1 if right & 1: right -= 1 self._all_apply(right, f) left >>= 1 right >>= 1 left = l2 right = r2 for i in range(1, self._log + 1): if ((left >> i) << i) != left: self._update(left >> i) if ((right >> i) << i) != right: self._update((right - 1) >> i) def max_right( self, left: int, g: typing.Callable[[typing.Any], bool]) -> int: assert 0 <= left <= self._n assert g(self._e) if left == self._n: return self._n left += self._size for i in range(self._log, 0, -1): self._push(left >> i) sm = self._e first = True while first or (left & -left) != left: first = False while left % 2 == 0: left >>= 1 if not g(self._op(sm, self._d[left])): while left < self._size: self._push(left) left *= 2 if g(self._op(sm, self._d[left])): sm = self._op(sm, self._d[left]) left += 1 return left - self._size sm = self._op(sm, self._d[left]) left += 1 return self._n def min_left(self, right: int, g: typing.Any) -> int: assert 0 <= right <= self._n assert g(self._e) if right == 0: return 0 right += self._size for i in range(self._log, 0, -1): self._push((right - 1) >> i) sm = self._e first = True while first or (right & -right) != right: first = False right -= 1 while right > 1 and right % 2: right >>= 1 if not g(self._op(self._d[right], sm)): while right < self._size: self._push(right) right = 2 * right + 1 if g(self._op(self._d[right], sm)): sm = self._op(self._d[right], sm) right -= 1 return right + 1 - self._size sm = self._op(self._d[right], sm) return 0 def _update(self, k: int) -> None: self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1]) def _all_apply(self, k: int, f: typing.Any) -> None: self._d[k] = self._mapping(f, self._d[k]) if k < self._size: self._lz[k] = self._composition(f, self._lz[k]) def _push(self, k: int) -> None: self._all_apply(2 * k, self._lz[k]) self._all_apply(2 * k + 1, self._lz[k]) self._lz[k] = self._id n, m = map(int, input().split()) # n < m <= 2e5 A = [0] * m LR = [[-1, -1] for _ in range(m)] lst = [0] * (m+1) ans = 0 for i in range(n): a, l, r = map(int, input().split()) #0 <= a <= 1e8, 1 <= l <= r <= m A[i] = a LR[i] = [l-1, r] lst[l-1] += 1 lst[r] -= 1 ans += a * (r - l + 1) q = int(input()) # q <= 2e5 for i in range(1, m): lst[i] += lst[i-1] for i in range(m): ans -= A[i] * lst[i] I = [i for i in range(n)] st0 = LazySegTree(lambda a, b: a+b, 0, lambda a, b: a+b, lambda a, b: a+b, 0, A) st1 = LazySegTree(lambda a, b: a+b, 0, lambda a, b: a+b, lambda a, b: a+b, 0, lst[:-1]) for _ in range(q): x, y, u, v = map(int, input().split()) # x <= n, y <= m, 1 <= u <= v <= m x -= 1; y -= 1; u -= 1 x0 = I[x] I[x] = y x = x0 a = st0.get(x) ans += a * st1.get(x) - a * st1.get(y) st0.set(x, 0) st0.set(y, a) l, r = LR[x] st1.apply(l, r, -1) ans -= a * (r - l) - a * (v - u) ans += st0.prod(l, r) - st0.prod(u, v) st1.apply(u, v, 1) LR[y] = [u, v] print(ans) */ #include using namespace std; using ll = long long; struct LazySegTree { int n; int size; int logv; vector d; vector lz; vector seglen; LazySegTree() : n(0), size(0), logv(0) {} LazySegTree(const vector& v) { build(v); } void build(const vector& v) { n = (int)v.size(); logv = 0; while ((1 << logv) < n) ++logv; size = 1 << logv; d.assign(2 * size, 0); lz.assign(size, 0); seglen.assign(2 * size, 0); for (int i = 0; i < size; ++i) seglen[size + i] = (i < n ? 1 : 0); for (int i = size - 1; i >= 1; --i) seglen[i] = seglen[2*i] + seglen[2*i+1]; for (int i = 0; i < n; ++i) d[size + i] = v[i]; for (int i = size - 1; i >= 1; --i) d[i] = d[2*i] + d[2*i+1]; } void all_apply(int k, ll f) { if (f == 0) return; d[k] += f * seglen[k]; if (k < size) lz[k] += f; } void push(int k) { if (lz[k] != 0) { all_apply(2*k, lz[k]); all_apply(2*k+1, lz[k]); lz[k] = 0; } } void pull(int k) { d[k] = d[2*k] + d[2*k+1]; } void set_val(int p, ll x) { p += size; for (int i = logv; i >= 1; --i) push(p >> i); d[p] = x; for (int i = 1; i <= logv; ++i) pull(p >> i); } ll get(int p) { p += size; for (int i = logv; i >= 1; --i) push(p >> i); return d[p]; } ll prod(int l, int r) { if (l == r) return 0; l += size; r += size; for (int i = logv; i >= 1; --i) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } ll sml = 0, smr = 0; while (l < r) { if (l & 1) sml += d[l++]; if (r & 1) smr = d[--r] + smr; l >>= 1; r >>= 1; } return sml + smr; } void apply(int l, int r, ll f) { if (l == r) return; int l0 = l + size, r0 = r + size; for (int i = logv; i >= 1; --i) { if (((l0 >> i) << i) != l0) push(l0 >> i); if (((r0 >> i) << i) != r0) push((r0 - 1) >> i); } int L = l0, R = r0; while (L < R) { if (L & 1) { all_apply(L++, f); } if (R & 1) { all_apply(--R, f); } L >>= 1; R >>= 1; } for (int i = 1; i <= logv; ++i) { if (((l0 >> i) << i) != l0) pull(l0 >> i); if (((r0 >> i) << i) != r0) pull((r0 - 1) >> i); } } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; if (!(cin >> n >> m)) return 0; vector A(m, 0); vector> LR(m, {-1,-1}); vector lst(m+1, 0); ll ans = 0; for (int i = 0; i < n; ++i) { ll a; int l, r; cin >> a >> l >> r; A[i] = a; LR[i] = {l-1, r}; lst[l-1] += 1; lst[r] -= 1; ans += a * (r - l + 1); } int q; cin >> q; for (int i = 1; i < m; ++i) lst[i] += lst[i-1]; for (int i = 0; i < m; ++i) ans -= A[i] * lst[i]; vector I(n); for (int i = 0; i < n; ++i) I[i] = i; LazySegTree st0(vector(A.begin(), A.end())); vector lstm(m); for (int i = 0; i < m; ++i) lstm[i] = lst[i]; LazySegTree st1(lstm); for (int qi = 0; qi < q; ++qi) { int x, y, u, v; cin >> x >> y >> u >> v; --x; --y; --u; int x0 = I[x]; I[x] = y; x = x0; ll a = st0.get(x); ans += a * st1.get(x) - a * st1.get(y); st0.set_val(x, 0); st0.set_val(y, a); int l = LR[x].first; int r = LR[x].second; st1.apply(l, r, -1); ans -= a * ( (ll)(r - l) ) - a * ( (ll)(v - u) ); ans += st0.prod(l, r) - st0.prod(u, v); st1.apply(u, v, 1); LR[y] = {u, v}; cout << ans << '\n'; } return 0; }