Overview

For each shop, we choose one of “don’t buy,” “Takahashi buys,” or “Aoki buys,” and we want to find the number of plans where Takahashi buys at \(P\) shops, Aoki buys at \(Q\) shops, and their total amounts are equal.

After each update, we recalculate the answer using dynamic programming that processes shops from the beginning in order.

Observations

In an equal shopping plan, the following \(3\) things are important:

• The number of shops where Takahashi bought
• The number of shops where Aoki bought
• The difference between Takahashi’s total amount and Aoki’s total amount

Therefore, we manage:

\[ \text{difference} = \text{Takahashi's total amount} - \text{Aoki's total amount} \]

What we ultimately want to find is the number of cases where:

• The number of shops where Takahashi bought is \(P\)
• The number of shops where Aoki bought is \(Q\)
• The difference is \(0\)

Naively enumerating all shopping plans would be far too many, since there are multiple choices for each shop, and it would not finish in time.

On the other hand, this problem has the following small constraints:

• \(P \leq 3\)
• \(Q \leq 3\)
• The purchase amount is at most \(20\)

Therefore, each person’s total amount is at most

\[ 3 \times 20 = 60 \]

Thus, it is sufficient to consider only differences from \(-60\) to \(60\).

Also, although the updates seem to require fast update processing, there is the constraint

\[ N \times M \leq 2000 \]

Therefore, even if we redo the DP from scratch after each update, it is fast enough.

Algorithm

We define the DP as follows.

\[ dp[p][q][d] \]

represents the number of plans for the shops seen so far, where:

• Takahashi has bought at \(p\) shops
• Aoki has bought at \(q\) shops
• The amount difference is \(d - \text{OFF}\)

Since the difference ranges from \(-60\) to \(60\), we add

\[ \text{OFF} = 60 \]

to make it easier to handle as an array index.

That is, a difference of \(0\) corresponds to index \(60\).

In the initial state, no shops have been seen yet and no one has bought anything, so:

\[ dp[0][0][\text{OFF}] = 1 \]

For each shop \(i\), let the range be \([L_i, R_i]\).

From the current state \(dp[p][q][d]\), we perform the following \(3\) types of transitions.

1. No one buys

\[ ndp[p][q][d] += dp[p][q][d] \]

2. Takahashi buys at amount \(a\)

When \(p < P\), for each \(a \in [L_i, R_i]\):

\[ ndp[p+1][q][d+a] += dp[p][q][d] \]

Since Takahashi’s total amount increases, the difference also increases by \(a\).

3. Aoki buys at amount \(a\)

When \(q < Q\), for each \(a \in [L_i, R_i]\):

\[ ndp[p][q+1][d-a] += dp[p][q][d] \]

Since Aoki’s total amount increases, the difference decreases by \(a\).

After processing all shops, the answer is

\[ dp[P][Q][\text{OFF}] \]

This represents the number of plans where Takahashi buys at \(P\) shops, Aoki buys at \(Q\) shops, and the difference is \(0\), meaning their total amounts are equal.

For each update, after replacing the interval \([L_X, R_X]\) of the specified shop with the new \([A, B]\), we recalculate this DP from scratch.

Complexity

Let the number of possible purchase amounts be \(V = 20\), and the number of difference states be

\[ D = 121 \]

• Time complexity: \(O(M \times N \times (P+1)(Q+1) \times D \times V)\)
• Space complexity: \(O((P+1)(Q+1) \times D)\)

\(P, Q, V, D\) are all small constants, and furthermore \(N \times M \leq 2000\), so this is fast enough.

Implementation Notes

• Since the difference can be negative, we add OFF = 60 to manage it as an index.

  • Difference \(0\) is OFF
  • Difference \(+a\) is OFF + a
  • Difference \(-a\) is OFF - a

• For each shop, we create a new ndp and perform transitions into it.

  • This prevents transitions where both Takahashi and Aoki buy at the same shop simultaneously.

• Since the answer can be extremely large, we always take the remainder modulo \(998244353\).

• Updates are cumulative, so we directly modify the arrays L, R and then execute the DP.

  Source Code

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

static const int MOD = 998244353;
static const int OFF = 60;
static const int W = OFF * 2 + 1;

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

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

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

    auto solve = [&]() -> int {
        int dp[4][4][W] = {};
        int ndp[4][4][W] = {};

        dp[0][0][OFF] = 1;

        for (int i = 0; i < N; i++) {
            memset(ndp, 0, sizeof(ndp));

            for (int p = 0; p <= P; p++) {
                for (int q = 0; q <= Q; q++) {
                    for (int d = 0; d < W; d++) {
                        int val = dp[p][q][d];
                        if (!val) continue;

                        int &none = ndp[p][q][d];
                        none += val;
                        if (none >= MOD) none -= MOD;

                        if (p < P) {
                            for (int a = L[i]; a <= R[i]; a++) {
                                if (d + a < W) {
                                    int &to = ndp[p + 1][q][d + a];
                                    to += val;
                                    if (to >= MOD) to -= MOD;
                                }
                            }
                        }

                        if (q < Q) {
                            for (int a = L[i]; a <= R[i]; a++) {
                                if (d - a >= 0) {
                                    int &to = ndp[p][q + 1][d - a];
                                    to += val;
                                    if (to >= MOD) to -= MOD;
                                }
                            }
                        }
                    }
                }
            }

            memcpy(dp, ndp, sizeof(dp));
        }

        return dp[P][Q][OFF];
    };

    for (int j = 0; j < M; j++) {
        int X, A, B;
        cin >> X >> A >> B;
        --X;
        L[X] = A;
        R[X] = B;
        cout << solve() << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.