Overview

This problem is solved by constructing a dynamic programming (DP) approach that processes each store with three choices: “don’t use,” “Takahashi uses,” or “Aoki uses,” and then efficiently answering update queries by “removing and reapplying the contribution of a store.”
The key insight is that since \(P, Q \le 3\) and the maximum amount is 20, the range of the total difference remains small.

Analysis

First, the condition “Takahashi’s total amount = Aoki’s total amount” can be rephrased by tracking the difference [ d = (\text{Takahashi’s total}) - (\text{Aoki’s total}) ] as “at the end, \(d = 0\).”

1. Basic DP

When processing stores from left to right, the state consists of: - Number of stores Takahashi has used: \(p\) - Number of stores Aoki has used: \(q\) - Difference: \(d\)

For each store \((L_i, R_i)\), there are three transitions:

1. Nobody uses it: state remains unchanged
2. Takahashi uses it: \(p \to p+1,\ d \to d+v\ (L_i \le v \le R_i)\)
3. Aoki uses it: \(q \to q+1,\ d \to d-v\ (L_i \le v \le R_i)\)

The final answer is \(\mathrm{dp}[P][Q][0]\).

2. Naive recomputation per query is too slow

If we rebuild the DP from scratch for all stores on every query, it takes roughly [ O(M \cdot N \cdot P \cdot Q \cdot D \cdot 20) ] time, which is borderline to infeasible given the constraints.

3. Adding and removing “the effect of one store”

This is the core idea of the solution.

If we view the processing of one store as a linear transformation \(F_i\), the overall result is [ \text{coeff} = F_N \circ \cdots \circ F_1 (\text{initial vector}) ] When a query changes only the range of store \(x\): - Remove the old \(F_x\) via its inverse operation - Reapply the new \(F_x\)

and we’re done.

Why the inverse operation is possible

Applying one store has the form [ \text{new} = \text{old} + T(\text{old}) ] (the “don’t use” component + the “use” component), where \(T\) always increments either \(p\) or \(q\) by 1.
This means the dependency goes in one direction: from smaller \((p, q)\) to larger \((p, q)\).
Therefore, we can recover values starting from old[0][0] in order (think of it as forward substitution in a system of linear equations in topological order).

This makes unapply_store possible, enabling efficient updates.

Algorithm

1. Fix the range of differences.
   Since \(P, Q \le 3\) and the maximum amount is 20,
   [ d \in [-60, 60] ] is sufficient.
2. Let coeff[p][q][d] be “the number of ways reflecting all stores processed so far.”
3. Initial state: coeff[0][0][0] = 1.
4. Execute apply_store(L[i], R[i]) for all stores in order to build the initial state.
5. For each query:
   • unapply_store(old L[x], old R[x])
   • Update the range
   • apply_store(new L[x], new R[x])
   • Output coeff[P][Q][0]

apply_store starts with nxt = coeff (preserving the “don’t use this store” component), then adds the transitions for using the store.
unapply_store reconstructs old using the forward recovery described above, then sets coeff = old.

Complexity

• Time complexity:
  Initial construction is \(O(N \cdot P \cdot Q \cdot D \cdot 20)\),
  each query takes a similar amount for unapply + apply
  [ O\big((N+M)\cdot P\cdot Q\cdot D\cdot 20\big) ] (Here \(D = 121,\ P, Q \le 3\), so this is fast enough.)
• Space complexity:
  [ O(P\cdot Q\cdot D) ]

Implementation Notes

• Since the difference array handles negative numbers, use an offset like didx(d) = d - DMIN.

• In unapply_store, it is important to fill old in the order p = 0..P, q = 0..Q (because dependencies only come from smaller values).

• Apply corrections as needed to prevent negative values in modular arithmetic.

• The sign argument in the code is unused, but logically the implementation clearly separates apply and unapply.

  Source Code

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 998244353;

int addmod(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
int submod(int a, int b){ a -= b; if(a < 0) a += MOD; return a; }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, P, Q, M;
    cin >> N >> P >> Q >> M;

    vector<int> L(N+1), R(N+1);
    for(int i=1;i<=N;i++) cin >> L[i] >> R[i];

    vector<int> X(M+1), A(M+1), B(M+1);
    for(int j=1;j<=M;j++) cin >> X[j] >> A[j] >> B[j];

    const int DMIN = -60, DMAX = 60, DSZ = DMAX - DMIN + 1;
    auto didx = [&](int d){ return d - DMIN; };

    vector<vector<vector<int>>> coeff(P+1, vector<vector<int>>(Q+1, vector<int>(DSZ, 0)));
    coeff[0][0][didx(0)] = 1;

    auto apply_store = [&](int l, int r, int sign)->void{
        vector<vector<vector<int>>> nxt = coeff;
        for(int p=0;p<=P;p++){
            for(int q=0;q<=Q;q++){
                for(int d=DMIN; d<=DMAX; d++){
                    int cur = coeff[p][q][didx(d)];
                    if(!cur) continue;

                    if(p < P){
                        for(int v=l; v<=r; v++){
                            int nd = d + v;
                            if(nd < DMIN || nd > DMAX) continue;
                            int &ref = nxt[p+1][q][didx(nd)];
                            ref += cur;
                            if(ref >= MOD) ref -= MOD;
                        }
                    }
                    if(q < Q){
                        for(int v=l; v<=r; v++){
                            int nd = d - v;
                            if(nd < DMIN || nd > DMAX) continue;
                            int &ref = nxt[p][q+1][didx(nd)];
                            ref += cur;
                            if(ref >= MOD) ref -= MOD;
                        }
                    }
                }
            }
        }
        coeff.swap(nxt);
    };

    auto unapply_store = [&](int l, int r, int sign)->void{
        // inverse of apply: coeff <- coeff - transitions from old state
        // Since apply is linear: new = old + T(old), inverse can be done by
        // old = new - T(old) in increasing (p+q) order:
        // because T only goes to larger p or q, we can reconstruct old in topological order.
        vector<vector<vector<int>>> old(P+1, vector<vector<int>>(Q+1, vector<int>(DSZ, 0)));

        for(int p=0;p<=P;p++){
            for(int q=0;q<=Q;q++){
                for(int d=DMIN; d<=DMAX; d++){
                    int val = coeff[p][q][didx(d)];

                    if(p > 0){
                        long long sub = 0;
                        for(int v=l; v<=r; v++){
                            int pd = d - v;
                            if(pd < DMIN || pd > DMAX) continue;
                            sub += old[p-1][q][didx(pd)];
                        }
                        val = (int)((val - sub) % MOD);
                        if(val < 0) val += MOD;
                    }
                    if(q > 0){
                        long long sub = 0;
                        for(int v=l; v<=r; v++){
                            int pd = d + v;
                            if(pd < DMIN || pd > DMAX) continue;
                            sub += old[p][q-1][didx(pd)];
                        }
                        val = (int)((val - sub) % MOD);
                        if(val < 0) val += MOD;
                    }

                    old[p][q][didx(d)] = val;
                }
            }
        }
        coeff.swap(old);
    };

    for(int i=1;i<=N;i++) apply_store(L[i], R[i], +1);

    for(int j=1;j<=M;j++){
        int x = X[j];
        unapply_store(L[x], R[x], -1);
        L[x] = A[j];
        R[x] = B[j];
        apply_store(L[x], R[x], +1);

        cout << coeff[P][Q][didx(0)] << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.