/* Original Python Code: # 自作ライブラリ # https://github.com/takumi-okamoto/competitive-programming-public/tree/main/mylib import sys # from atcoder.fenwicktree import FenwickTree # from atcoder.lazysegtree import LazySegTree # sys.setrecursionlimit(10**8) import typing # https://github.com/not522/ac-library-python/blob/master/atcoder/fenwicktree.py class FenwickTree:     """Reference: https://en.wikipedia.org/wiki/Fenwick_tree"""     def __init__(self, n: int = 0) -> None:         self._n = n         self.data = [0] * n     def add(self, p: int, x: typing.Any) -> None:         assert 0 <= p < self._n         p += 1         while p <= self._n:             self.data[p - 1] += x             p += p & -p     def sum(self, left: int, right: int) -> typing.Any:         assert 0 <= left <= right <= self._n         return self._sum(right) - self._sum(left)     def _sum(self, r: int) -> typing.Any:         s = 0         while r > 0:             s += self.data[r - 1]             r -= r & -r         return s # https://github.com/not522/ac-library-python/blob/master/atcoder/_bit.py def _ceil_pow2(n: int) -> int:     x = 0     while (1 << x) < n:         x += 1     return x # https://github.com/not522/ac-library-python/blob/master/atcoder/lazysegtree.py # を一部改変 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] = self._mapping(f, self._d[p])         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 def debug(*args):     print(*args, file=sys.stderr) def main():     n, m = map(int, input().split())     a = []     l = []     r = []     for _ in range(n):         ai, li, ri = map(int, input().split())         a.append(ai)         l.append(li - 1)         r.append(ri)     b = FenwickTree(m)     for i in range(n):         b.add(i, a[i])     INF = 10**18     counter = LazySegTree(         op=lambda v1, v2: min(v1, v2),         mapping=lambda f, v: f + v,         composition=lambda f, g: f + g,         e=INF,         id_=0,         v=[0] * m,     )     # 初期化     ans = 0     pos = [None] * m     inv_pos = dict()     for i in range(n):         ai, li, ri = a[i], l[i], r[i]         ans += ai * (ri - li) - b.sum(li, ri)         counter.apply(li, ri, 1)         pos[i] = i         inv_pos[i] = i     # debug(ans)     # debug(counter)     # debug("counter", [counter.get(i) for i in range(m)])     # debug("b", [b.sum(i, i + 1) for i in range(m)])     q = int(input())     for _ in range(q):         x, y, u, v = map(int, input().split())         x -= 1         y -= 1         u -= 1         # 自分のレートの幅の差分         ans += a[x] * (v - u) - a[x] * (r[x] - l[x])         # 自分に対する相対基準の幅の差分         ans += b.sum(l[x], r[x])         pre_house = pos[x]         # 自分が相対基準だったとこ         counter.apply(l[x], r[x], -1)         ans += a[x] * counter.get(pre_house)         # 自分が相対基準になるところ         ans -= a[x] * counter.get(y)         counter.apply(u, v, 1)         # お家の移動         b.add(pre_house, -a[x])         b.add(y, a[x])         ans -= b.sum(u, v)         pos[x] = y         inv_pos[y] = x         l[x], r[x] = u, v         print(ans)         # debug("counter", [counter.get(i) for i in range(m)])         # debug("b", [b.sum(i, i + 1) for i in range(m)]) if __name__ == "__main__":     main() */ #include #include #include #include #include #include #include // Reference: https://en.wikipedia.org/wiki/Fenwick_tree class FenwickTree { private: int _n; std::vector data; long long _sum(int r) { long long s = 0; while (r > 0) { s += data[r - 1]; r -= r & -r; } return s; } public: FenwickTree(int n = 0) : _n(n), data(n, 0) {} void add(int p, long long x) { assert(0 <= p && p < _n); p++; while (p <= _n) { data[p - 1] += x; p += p & -p; } } long long sum(int left, int right) { assert(0 <= left && left <= right && right <= _n); return _sum(right) - _sum(left); } }; int ceil_pow2(int n) { int x = 0; while ((1 << x) < n) { x++; } return x; } template class LazySegTree { private: int _n; int _log; int _size; std::vector _d; std::vector _lz; Op _op; S _e; Mapping _mapping; Composition _composition; F _id; void _update(int k) { _d[k] = _op(_d[2 * k], _d[2 * k + 1]); } void _all_apply(int k, F f) { _d[k] = _mapping(f, _d[k]); if (k < _size) { _lz[k] = _composition(f, _lz[k]); } } void _push(int k) { _all_apply(2 * k, _lz[k]); _all_apply(2 * k + 1, _lz[k]); _lz[k] = _id; } public: LazySegTree(int n, Op op, S e, Mapping mapping, Composition composition, F id) : _n(n), _op(op), _e(e), _mapping(mapping), _composition(composition), _id(id) { _log = ceil_pow2(_n); _size = 1 << _log; _d.assign(2 * _size, _e); _lz.assign(_size, _id); } LazySegTree(const std::vector& v, Op op, S e, Mapping mapping, Composition composition, F id) : _n(v.size()), _op(op), _e(e), _mapping(mapping), _composition(composition), _id(id) { _log = ceil_pow2(_n); _size = 1 << _log; _d.assign(2 * _size, _e); _lz.assign(_size, _id); for (int i = 0; i < _n; i++) { _d[_size + i] = v[i]; } for (int i = _size - 1; i > 0; i--) { _update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += _size; for (int i = _log; i > 0; i--) { _push(p >> i); } _d[p] = x; for (int i = 1; i <= _log; i++) { _update(p >> i); } } S get(int p) { assert(0 <= p && p < _n); p += _size; for (int i = _log; i > 0; i--) { _push(p >> i); } return _d[p]; } S prod(int left, int right) { assert(0 <= left && left <= right && right <= _n); if (left == right) { return _e; } left += _size; right += _size; for (int i = _log; i > 0; i--) { if (((left >> i) << i) != left) _push(left >> i); if (((right >> i) << i) != right) _push((right - 1) >> i); } S sml = _e, smr = _e; while (left < right) { if (left & 1) { sml = _op(sml, _d[left]); left++; } if (right & 1) { right--; smr = _op(_d[right], smr); } left >>= 1; right >>= 1; } return _op(sml, smr); } S all_prod() { return _d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += _size; for (int i = _log; i > 0; i--) { _push(p >> i); } _d[p] = _mapping(f, _d[p]); for (int i = 1; i <= _log; i++) { _update(p >> i); } } void apply(int left, int right, F f) { assert(0 <= left && left <= right && right <= _n); if (left == right) { return; } left += _size; right += _size; for (int i = _log; i > 0; i--) { if (((left >> i) << i) != left) _push(left >> i); if (((right >> i) << i) != right) _push((right - 1) >> i); } { int l2 = left; int r2 = right; while (left < right) { if (left & 1) { _all_apply(left, f); left++; } if (right & 1) { right--; _all_apply(right, f); } left >>= 1; right >>= 1; } left = l2; right = r2; } for (int i = 1; i <= _log; i++) { if (((left >> i) << i) != left) _update(left >> i); if (((right >> i) << i) != right) _update((right - 1) >> i); } } int max_right(int left, std::function g) { assert(0 <= left && left <= _n); assert(g(_e)); if (left == _n) { return _n; } left += _size; for (int i = _log; i > 0; i--) { _push(left >> i); } S sm = _e; bool first = true; while (first || (left & -left) != left) { first = false; while (left % 2 == 0) { left >>= 1; } if (!g(_op(sm, _d[left]))) { while (left < _size) { _push(left); left *= 2; if (g(_op(sm, _d[left]))) { sm = _op(sm, _d[left]); left++; } } return left - _size; } sm = _op(sm, _d[left]); left++; } return _n; } int min_left(int right, std::function g) { assert(0 <= right && right <= _n); assert(g(_e)); if (right == 0) { return 0; } right += _size; for (int i = _log; i > 0; i--) { _push((right - 1) >> i); } S sm = _e; bool first = true; while (first || (right & -right) != right) { first = false; right--; while (right > 1 && right % 2) { right >>= 1; } if (!g(_op(_d[right], sm))) { while (right < _size) { _push(right); right = 2 * right + 1; if (g(_op(_d[right], sm))) { sm = _op(_d[right], sm); right--; } } return right + 1 - _size; } sm = _op(_d[right], sm); } return 0; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int n, m; std::cin >> n >> m; std::vector a(n); std::vector l(n); std::vector r(n); for (int i = 0; i < n; ++i) { std::cin >> a[i] >> l[i] >> r[i]; l[i]--; } FenwickTree b(m); for (int i = 0; i < n; ++i) { b.add(i, a[i]); } const long long INF = 1000000000000000000LL; auto op = [](long long v1, long long v2) { return std::min(v1, v2); }; auto mapping = [](long long f, long long v) { return f + v; }; auto composition = [](long long f, long long g) { return f + g; }; std::vector initial_v(m, 0); LazySegTree counter(initial_v, op, INF, mapping, composition, 0); long long ans = 0; std::vector pos(n); std::map inv_pos; for (int i = 0; i < n; ++i) { long long ai = a[i]; int li = l[i]; int ri = r[i]; ans += ai * (ri - li) - b.sum(li, ri); counter.apply(li, ri, 1LL); pos[i] = i; inv_pos[i] = i; } int q; std::cin >> q; for (int i = 0; i < q; ++i) { int x, y, u, v; std::cin >> x >> y >> u >> v; x--; y--; u--; ans += a[x] * (v - u) - a[x] * (r[x] - l[x]); ans += b.sum(l[x], r[x]); int pre_house = pos[x]; counter.apply(l[x], r[x], -1LL); ans += a[x] * counter.get(pre_house); ans -= a[x] * counter.get(y); counter.apply(u, v, 1LL); b.add(pre_house, -a[x]); b.add(y, a[x]); ans -= b.sum(u, v); pos[x] = y; inv_pos[y] = x; l[x] = u; r[x] = v; std::cout << ans << "\n"; } }