#ifdef ONLINE_JUDGE #include #include #elif defined(LOCAL) #include #endif // ―――――――――――――――――――――――――――――――― // abbreviation // ―――――――――――――――――――――――――――――――― using namespace std; using namespace atcoder; using ll = long long; template using V = vector; template using VV = vector>; using vi = vector; using vl = vector; using vd = V; using vs = V; using vc = V; using vvi = vector>; using vvl = vector>; using vvc = vector>; using si = set; using mi = multiset; template using minpq = priority_queue, greater>; using mint = modint998244353; using vm = V; using vvm = VV; // ―――――――――――――――――――――――――――――――― // P // ―――――――――――――――――――――――――――――――― template struct P : pair { template P(Args... args) : pair(args...) { } using pair::first; using pair::second; P& operator+=(const P& r) { first += r.first; second += r.second; return *this; } P& operator-=(const P& r) { first -= r.first; second -= r.second; return *this; } P& operator*=(const P& r) { first *= r.first; second *= r.second; return *this; } template P& operator*=(const S& r) { first *= r, second *= r; return *this; } P operator+(const P& r) const { return P(*this) += r; } P operator-(const P& r) const { return P(*this) -= r; } P operator*(const P& r) const { return P(*this) *= r; } template P operator*(const S& r) const { return P(*this) *= r; } P operator-() const { return P{-first, -second}; } }; using pl = P; using pi = P; using vp = V; // ―――――――――――――――――――――――――――――――― // preprocessor // ―――――――――――――――――――――――――――――――― #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define call(v) (v).cbegin(), (v).cend() #define each(i, v) for (auto i : (v)) #define each2(x, y, v) for (auto [x, y] : (v)) #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define repr(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--) #define repit(i, v) for (auto i = v.begin(); i < v.end(); i++) #define reprit(i, v) for (auto i = v.rbegin(); i < v.rend(); i++) #define reg(i, l, r) for (ll i = (ll)(l); i < (ll)(r); i++) #define regr(i, l, r) for (ll i = (ll)(r) - 1; i >= (ll)(l); i--) #define regit(i, l, r) for (auto i = (l); i != (r); i++) #define regrit(i, l, r) for (auto i = make_reverse_iterator((r)); i != make_reverse_iterator((l)); i++) #define REP(i, n) for (ll i = 0; i <= (ll)(n); i++) #define REPR(i, n) for (ll i = (ll)(n); i >= 0; i--) #define REG(i, l, r) for (ll i = (ll)(l); i <= (ll)(r); i++) #define REGR(i, l, r) for (ll i = (ll)(r); i >= (ll)(l); i--) #define Yes cout << "Yes" << el #define No cout << "No" << el #define YES cout << "YES" << el #define NO cout << "NO" << el #define fls cout << flush #define eps (1e-10) #define Equals(a, b) (fabs((a) - (b)) < eps) #define MAX(x) *max_element(all(x)) #define MIN(x) *min_element(all(x)) #define BIT(n) (1LL << (n)) #define between(l, k, r) (l <= k && k < r) #define pb push_back // #define fi first // #define se second // ―――――――――――――――――――――――――――――――― // constexpr // ―――――――――――――――――――――――――――――――― constexpr int INF = 0x3f3f3f3f; constexpr ll LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr string_view ascii_lowercase = "abcdefghijklmnopqrstuvwxyz"; constexpr string_view ascii_uppercase = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; constexpr char el = '\n'; constexpr char spa = ' '; // ―――――――――――――――――――――――――――――――― // yn, YN // ―――――――――――――――――――――――――――――――― bool yn(const bool b) { if (b) { Yes; } else { No; } return b; } bool YN(const bool b) { if (b) { YES; } else { NO; } return b; } // ―――――――――――――――――――――――――――――――― // chmax, chmin // ―――――――――――――――――――――――――――――――― template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; } // ―――――――――――――――――――――――――――――――― // operator <<, >> overload // ―――――――――――――――――――――――――――――――― template istream& operator>>(istream& is, V& v) { T x; is >> x; v.push_back(x); return is; } template ostream& operator<<(ostream& os, const V& v) { if (&os == &cout) { rep(i, v.size()) { os << v[i]; if (i != v.size() - 1) os << ' '; } return os; } else { os << "["; rep(i, v.size()) { os << v[i]; if (i != v.size() - 1) os << ", "; } return os << "]"; } } template istream& operator>>(istream& is, pair& p) { return is >> p.first >> p.second; } template ostream& operator<<(ostream& os, const pair& p) { if (&os == &cout) return os << p.first << ' ' << p.second; else return os << "(" << p.first << ", " << p.second << ")"; } template istream& operator>>(istream& is, tuple& t) { apply( [&](const auto&... args) { size_t n = 0; ((is >> args), ...); }, t); return is; } template ostream& operator<<(ostream& os, const tuple& t) { if (&os == &cout) { apply( [&](const auto&... args) { size_t n = 0; ((os << (n++ ? " " : "") << args), ...); }, t); return os << ")"; } else { os << "("; apply( [&](const auto&... args) { size_t n = 0; ((os << (n++ ? ", " : "") << args), ...); }, t); return os << ")"; } } template istream& operator>>(istream& is, static_modint& m) { int x; is >> x; m = static_modint(x); return is; } template ostream& operator<<(ostream& os, const static_modint& m) { return os << m.val(); } // ―――――――――――――――――――――――――――――――― // factotrial // ―――――――――――――――――――――――――――――――― vm fact, invf; void fact_init(int m = 200000) { fact.resize(m + 1); invf.resize(m + 1); fact[0] = 1; rep(i, m) fact[i + 1] = fact[i] * (i + 1); invf[m] = fact[m].inv(); repr(i, m) invf[i] = invf[i + 1] * (i + 1); } mint comb(int n, int r) { if (r < 0 || n < r) return 0; return fact[n] * invf[r] * invf[n - r]; } mint noadj(int n, int r) { return comb(n - r + 1, r); } // ―――――――――――――――――――――――――――――――― // Fibonacci // ―――――――――――――――――――――――――――――――― vm fib; void fib_init(int m = 200000) { fib.resize(m + 1); fib[0] = 0; fib[1] = 1; rep(i, m) fib[i + 2] = fib[i] + fib[i + 1]; } // ―――――――――――――――――――――――――――――――― // monoid // ―――――――――――――――――――――――――――――――― namespace monoid { struct S { ll value; int len; }; using F = int; S op(S l, S r) { return S{ l.value + r.value, l.len + r.len, }; } S e() { return S{0, 0}; } S mapping(F l, S r) { return S{ r.value + l * r.len, r.len, }; } F composition(F l, F r) { return l + r; } F id() { return 0; } } // namespace monoid // ―――――――――――――――――――――――――――――――― // ACL // ―――――――――――――――――――――――――――――――― // #include // #include #include // #include // #include // #include // #include // #include // #include // #include // #include int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(10) << boolalpha; cerr << fixed << setprecision(10) << boolalpha; int N, M; cin >> N >> M; vl A; vp itv; rep(i, N) { cin >> A >> itv; itv[i].first--; } vi H(N); rep(i, N) H[i] = i; vi C(M + 1, 0); each2(l, r, itv) { C[l]++; C[r]--; } rep(i, M) C[i + 1] += C[i]; ll ans = 0; rep(i, N) { int a = A[i]; auto [l, r] = itv[i]; int c = C[i]; ans += (r - l - c) * a; } lazy_segtree< monoid::S, monoid::op, monoid::e, monoid::F, monoid::mapping, monoid::composition, monoid::id> TB(M); lazy_segtree< monoid::S, monoid::op, monoid::e, monoid::F, monoid::mapping, monoid::composition, monoid::id> TC(M); rep(i, N) TB.set(i, monoid::S{A[i], 1}); rep(i, M) TC.set(i, monoid::S{C[i], 1}); int Q; cin >> Q; cerr << ans << el; rep(i, Q) { int x, y, u, v; cin >> x >> y >> u >> v; x--; y--; u--; ll a = A[x]; int yy = H[x]; H[x] = y; auto [l, r] = itv[x]; itv[x] = make_pair(u, v); ans += ((v - u) - (r - l)) * a; ans += TB.prod(l, r).value; TB.set(yy, monoid::S{0, 1}); TB.set(y, monoid::S{a, 1}); ans -= TB.prod(u, v).value; TC.apply(l, r, -1); ans -= (TC.get(y).value - TC.get(yy).value) * a; TC.apply(u, v, 1); cout << ans << el; } return 0; }