import types _atcoder_code = """ # Python port of AtCoder Library. __version__ = '0.0.1' """ atcoder = types.ModuleType("atcoder") exec(_atcoder_code, atcoder.__dict__) _atcoder__bit_code = """ 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 """ atcoder._bit = types.ModuleType("atcoder._bit") exec(_atcoder__bit_code, atcoder._bit.__dict__) _atcoder_lazysegtree_code = """ import typing # import atcoder._bit 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 = atcoder._bit._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 >> 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 """ atcoder.lazysegtree = types.ModuleType("atcoder.lazysegtree") atcoder.lazysegtree.__dict__["atcoder"] = atcoder atcoder.lazysegtree.__dict__["atcoder._bit"] = atcoder._bit exec(_atcoder_lazysegtree_code, atcoder.lazysegtree.__dict__) LazySegTree = atcoder.lazysegtree.LazySegTree _atcoder_segtree_code = """ import typing # import atcoder._bit class SegTree: def __init__(self, op: typing.Callable[[typing.Any, typing.Any], typing.Any], e: typing.Any, v: typing.Union[int, typing.List[typing.Any]]) -> None: self._op = op self._e = e if isinstance(v, int): v = [e] * v self._n = len(v) self._log = atcoder._bit._ceil_pow2(self._n) self._size = 1 << self._log self._d = [e] * (2 * 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 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 return self._d[p + self._size] def prod(self, left: int, right: int) -> typing.Any: assert 0 <= left <= right <= self._n sml = self._e smr = self._e left += self._size right += self._size 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 max_right(self, left: int, f: typing.Callable[[typing.Any], bool]) -> int: assert 0 <= left <= self._n assert f(self._e) if left == self._n: return self._n left += self._size sm = self._e first = True while first or (left & -left) != left: first = False while left % 2 == 0: left >>= 1 if not f(self._op(sm, self._d[left])): while left < self._size: left *= 2 if f(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, f: typing.Callable[[typing.Any], bool]) -> int: assert 0 <= right <= self._n assert f(self._e) if right == 0: return 0 right += self._size 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 f(self._op(self._d[right], sm)): while right < self._size: right = 2 * right + 1 if f(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]) """ atcoder.segtree = types.ModuleType("atcoder.segtree") atcoder.segtree.__dict__["atcoder"] = atcoder atcoder.segtree.__dict__["atcoder._bit"] = atcoder._bit exec(_atcoder_segtree_code, atcoder.segtree.__dict__) SegTree = atcoder.segtree.SegTree # from atcoder.lazysegtree import LazySegTree # from atcoder.segtree import SegTree n, m = map(int, input().split()) rate = [0] * m each_range = [(0, 0)] * m pos = [0] * m ID = 0 # (sum, length) def op(x, y): return (x[0] + y[0], x[1] + y[1]) def e(): return (0, 0) def mapping(f, x): if f == ID: return x return (f * x[1] + x[0], x[1]) def composition(f_new, f_old): if f_new == ID: return f_old return f_new + f_old lst = LazySegTree(op, e(), mapping, composition, ID, [(0, 1)] * m) for i in range(n): a, l, r = map(int, input().split()) rate[i] = a pos[i] = i each_range[i] = (l, r) lst.apply(l - 1, r, 1) # for i in range(m): # print(lst.get(i), end=" ") # exit() st = SegTree(lambda x, y: x + y, 0, rate) crr_ans = 0 for i in range(m): if rate[i] == 0: continue l, r = each_range[i] crr_ans += rate[i] * (r - l + 1) - st.prod(l - 1, r) ans = [] q = int(input()) for _ in range(q): x, y, u, v = map(int, input().split()) x -= 1 y -= 1 px = pos[x] # 何人の範囲にかぶっていたか l, r = each_range[px] minus = lst.get(px)[0] if l - 1 <= px < r: minus -= 1 crr_ans += rate[px] * minus lst.apply(l - 1, r, -1) # 引っ越す前の本人の天才度 crr_ans -= rate[px] * (r - l + 1) - st.prod(l - 1, r) # レート更新とか rate[y] = rate[px] rate[px] = 0 st.set(px, 0) st.set(y, rate[y]) each_range[px] = (0, 0) each_range[y] = (u, v) # 何人の範囲にかぶっているか crr_ans -= rate[y] * lst.get(y)[0] lst.apply(u - 1, v, 1) # 引っ越した後の天才度 crr_ans += rate[y] * (v - u + 1) - st.prod(u - 1, v) pos[x] = y ans.append(crr_ans) print(*ans, sep="\n")