#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG //[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意 #endif #include #include #include // M_PIを使用するため using namespace std; using ll = long long; using ld = long double; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define rrep(i, n) for (ll i = (ll)n - 1; i >= 0; --i) const ll INF = (1LL << 62); const ll null = -1LL; template using vc = vector; // prioriy_queueに必要なのでここにこれ書いてます template using vv = vc>; template using vvv = vv>; using vl = vc; using vvl = vv; using vvvl = vv; using vvvvl = vv; using vs = vc; using vvs = vv; using vb = vc; using vvb = vc; using P = pair; template istream &operator>>(istream &i, vc &v) { rep(j, size(v)) i >> v[j]; return i; } // それぞれ「下,上,右,左」に対応 int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; #define nall(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() template bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } #define pb push_back #define eb emplace_back #define em emplace #define pob pop_back #define next_p(v) next_permutation(v.begin(), v.end()) ll seg_len = (1ll << 18); vl seg2(seg_len * 2ll, 0); ll get(ll pos) { return seg2[pos + seg_len]; } void update(ll pos, ll val) { pos += seg_len; seg2[pos] = val; pos /= 2ll; while (pos > 1ll) { seg2[pos] = seg2[pos * 2] + seg2[pos * 2 + 1ll]; pos /= 2ll; } } ll get_sum(ll ql, ll qr, ll sl = 0, ll sr = seg_len, ll pos = 1ll) { if (sr <= ql || qr <= sl) return 0; if (ql <= sl && sr <= qr) return seg2[pos]; ll sm = (sl + sr) / 2ll; ll l_sum = get_sum(ql, qr, sl, sm, pos * 2ll); ll r_sum = get_sum(ql, qr, sm, sr, pos * 2ll + 1ll); return l_sum + r_sum; } vector seg(seg_len * 2, 0); // セグメントツリーの値を保持 vector lazy(seg_len * 2, 0); // 遅延伝播用の配列 // 遅延伝播の処理を行う関数 void propagate(int pos, int sl, int sr) { if (lazy[pos] != 0) { seg[pos] += lazy[pos]; // 遅延分を反映 if (sr - sl > 1) { // 葉ノードでない場合、子ノードに遅延を伝搬 lazy[pos * 2] += lazy[pos]; lazy[pos * 2 + 1] += lazy[pos]; } lazy[pos] = 0; // 自身の遅延をクリア } } // 区間 [l, r) に x を加算する関数(遅延伝播を使用) void add(int l, int r, ll x, int sl = 0, int sr = seg_len, int pos = 1) { propagate(pos, sl, sr); // まず遅延を処理 if (l >= sr || r <= sl) return; // 完全に区間外なら何もしない if (l <= sl && sr <= r) { // 完全に区間内なら遅延を適用 lazy[pos] += x; propagate(pos, sl, sr); // 遅延評価 } else { int sm = (sl + sr) / 2; add(l, r, x, sl, sm, pos * 2); // 左側の区間に適用 add(l, r, x, sm, sr, pos * 2 + 1); // 右側の区間に適用 seg[pos] = max(seg[pos * 2], seg[pos * 2 + 1]); // 親の値を更新 } } // 区間 [ql, qr) における最大値を取得する関数(遅延伝播を使用) ll get_max(int ql, int qr, int sl = 0, int sr = seg_len, int pos = 1) { propagate(pos, sl, sr); // 遅延を処理 if (ql >= sr || qr <= sl) return -INF; // 完全に区間外なら無視 if (ql <= sl && qr >= sr) return seg[pos]; // 完全に区間内ならそのまま返す int sm = (sl + sr) / 2; ll l_max = get_max(ql, qr, sl, sm, pos * 2); // 左側の最大値 ll r_max = get_max(ql, qr, sm, sr, pos * 2 + 1); // 右側の最大値 return max(l_max, r_max); // 左右の最大値のうち最大を返す } void solve() { ll n, m; cin >> n >> m; vl rate(n), l(n), r(n), pos(n); rep(i,n) { cin >> rate[i] >> l[i] >> r[i]; pos[i] = i; update(i,rate[i]); --l[i]; add(l[i],r[i],1ll); } ll ans = 0; rep(i,n) { ll len = r[i] - l[i]; ans += rate[i] * len - get_sum(l[i],r[i]); } ll q; cin >> q; rep(_,q) { ll i; cin >> i; --i; ll to; cin >> to; --to; add(l[i],r[i],-1ll); ans += get_max(pos[i],pos[i]+1ll) * rate[i]; ll pre = get(pos[i]); ans -= (r[i] - l[i]) * rate[i]; ans += get_sum(l[i],r[i]); update(pos[i],pre-rate[i]); pos[i] = to; cin >> l[i] >> r[i]; --l[i]; ans -= get_max(pos[i],pos[i] + 1ll) * rate[i]; pre = get(pos[i]); update(pos[i],pre + rate[i]); ans += (r[i] - l[i]) * rate[i]; ans -= get_sum(l[i],r[i]); add(l[i],r[i],1ll); cout << ans << endl; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll testcases = 1ll; // cin >> testcases; rep(_, testcases) solve(); return 0; }