#include using namespace std; using ll = long long; #ifdef LOCAL #include #else #define debug(...) #endif template struct BinaryIndexedTree { int N; vector data; BinaryIndexedTree() = default; BinaryIndexedTree(int size) : N(size), data(size + 1, 0) {} BinaryIndexedTree(const vector& v) : N(ssize(v)), data(N + 1) { for (int i = 1; i <= N; i++) { data[i] += v[i - 1]; int j = i + (i & -i); if (j <= N) data[j] += data[i]; } } // i 番目に x を加算 void add(int i, T x) { assert(0 <= i && i < N); for (++i; i <= N; i += i & -i) data[i] += x; } // i 番目を x に更新 void set(int i, T x) { assert(0 <= i && i < N); T diff = x - sum(i, i + 1); for (++i; i <= N; i += i & -i) data[i] += diff; } // [l, r) に x を加算 (imos 法) void imos(int l, int r, T x) { add(l, x), add(r, -x); } // [0, i) の和 (imos 法で区間加算して i 番目の値を取るときは sum(i + 1)) T sum(int i) const { if (i < 0) return T{}; T res{}; for (; i > 0; i -= i & -i) res += data[i]; return res; } // [l, r) の和 T sum(int l, int r) const { return sum(r) - sum(l); } // i 番目の値 T operator[](int i) const { return sum(i + 1) - sum(i); } // [0, i) の和が w 以上となる最小の i int lower_bound(T w) const { if (w <= 0) return 0; int i = 0; for (int k = 1 << __lg(N); k > 0; k >>= 1) { if (i + k <= N && data[i + k] < w) { w -= data[i + k]; i += k; } } return i + 1; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int N, M; cin >> N >> M; vector A(M), L(N), R(N); for (int i = 0; i < N; i++) cin >> A[i] >> L[i] >> R[i], L[i]--; int Q; cin >> Q; // H[i] := 家 i に住んでいる岩井星人の id vector H(M, -1); iota(H.begin(), H.begin() + N, 0); // I[i] := 岩井星人 i が住んでいる家の id vector I(N); iota(I.begin(), I.end(), 0); // 初期状態の天才度の総和を求める ll ans = 0; BinaryIndexedTree bit(A), bit2(M + 1); for (int i = 0; i < N; i++) { ans += (R[i] - L[i]) * A[I[i]] - (bit.sum(L[i], R[i])); } for (int i = 0; i < N; i++) { bit2.imos(L[i], R[i], 1); } while (Q--) { int X, Y, U, V; cin >> X >> Y >> U >> V, X--, Y--, U--; // 差分更新 // 岩井星人 X の天才度を reset // for (int j = L[X]; j < R[X]; j++) { // ans -= A[I[X]] - A[j]; // } ans -= (R[X] - L[X]) * A[I[X]] - (bit.sum(L[X], R[X])); // 地元 [L[i], R[i]) に I[X] が含まれている岩井星人 i の岩井星人 X に関する天才度を reset // for (int i = 0; i < N; i++) { // if (i == X) continue; // if (L[i] <= I[X] && I[X] < R[i]) { // // ans -= A[I[i]] - A[I[X]]; // // ans += A[I[i]]; // ans += A[I[X]]; // } // } ans += bit2.sum(I[X] + 1) * A[I[X]]; ans -= (L[X] <= I[X] && I[X] < R[X]) ? A[I[X]] : 0; swap(H[I[X]], H[Y]); A[Y] = A[I[X]], A[I[X]] = 0; bit.set(Y, A[Y]), bit.set(I[X], 0); I[X] = Y; bit2.imos(L[X], R[X], -1), bit2.imos(U, V, 1); L[X] = U, R[X] = V; // 岩井星人 X の天才度を set // for (int j = L[X]; j < R[X]; j++) { // ans += A[I[X]] - A[j]; // } ans += (R[X] - L[X]) * A[I[X]] - (bit.sum(L[X], R[X])); // 地元 [L[i], R[i]) に I[X] が含まれている岩井星人 i の岩井星人 X に関する天才度を set // for (int i = 0; i < N; i++) { // if (i == X) continue; // if (L[i] <= I[X] && I[X] < R[i]) { // // ans -= A[I[i]]; // // ans += A[I[i]] - A[I[X]]; // ans -= A[I[X]]; // } // } ans -= bit2.sum(I[X] + 1) * A[I[X]]; ans += (L[X] <= I[X] && I[X] < R[X]) ? A[I[X]] : 0; cout << ans << "\n"; } }