Overview

For each shop, we choose one of three options: “don’t buy,” “Takahashi buys,” or “Aoki buys,” and we count the number of plans where Takahashi’s and Aoki’s total purchase amounts are equal.

Since \(P,Q \leq 3\) and the maximum purchase amount is \(20\), which are small, we solve this with DP whose state tracks “how many shops have been selected” and “the difference in total amounts.”

Analysis

Let Takahashi’s total amount be \(S_T\) and Aoki’s total amount be \(S_A\).

For an equal shopping plan, we need:

\[ S_T = S_A \]

This can be rephrased as the difference

\[ S_T - S_A \]

being \(0\).

Therefore, we consider a DP that processes each shop in order while tracking the following:

• The number of shops Takahashi has already bought from
• The number of shops Aoki has already bought from
• The current amount difference \(S_T - S_A\)

For each shop, there are 3 possible choices:

1. Nobody buys
   → The state does not change
2. Takahashi buys at price \(x\)
   → Takahashi’s shop count increases by \(1\), and the difference increases by \(+x\)
3. Aoki buys at price \(x\)
   → Aoki’s shop count increases by \(1\), and the difference changes by \(-x\)

At the end, the answer is the number of states where:

• Takahashi has bought from \(P\) shops
• Aoki has bought from \(Q\) shops
• The difference is \(0\)

Range of the Difference

The maximum amount Takahashi can spend is \(20P\), and the maximum amount Aoki can spend is \(20Q\).

Therefore, the range of the difference \(S_T - S_A\) is:

\[ -20Q \leq S_T - S_A \leq 20P \]

Since negative indices are inconvenient to handle in arrays, in the code we shift by:

\[ \text{OFF} = 20Q \]

That is, a difference \(d\) is stored at index:

\[ d + \text{OFF} \]

in the array.

Why a Brute-Force Approach Is Infeasible

Each shop has 3 possible states, and when buying, there are up to 20 possible prices.

Enumerating all combinations would take exponential time, which is far too slow when \(N\) can be up to \(2000\).

On the other hand, since \(P,Q \leq 3\) and prices are at most \(20\), the number of necessary states is very small.

Therefore, we can count efficiently using DP.

Additionally, although there are \(M\) updates, the constraint guarantees:

\[ N \times M \leq 2000 \]

Thus, even if we recompute 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 shopping plans where:

• Takahashi has bought from \(p\) shops
• Aoki has bought from \(q\) shops
• The difference \(S_T - S_A\) is \(d\)

In the implementation, since \(d\) cannot be used directly as an index, we actually store it as:

\[ dp[p][q][d + \text{OFF}] \]

The initial state is that nobody has bought anything yet:

\[ dp[0][0][0] = 1 \]

When a shop has a purchasable price range of \([L,R]\), the transitions are as follows.

1. Nobody Buys

The state does not change.

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

In the code, this is realized by copying the current DP with ndp = [arr[:] for arr in dp].

2. Takahashi Buys

When Takahashi buys at price \(x\), the difference increases by \(+x\).

\[ dp[p][q][d] \to dp[p+1][q][d+x] \]

This applies only when \(p < P\).

3. Aoki Buys

When Aoki buys at price \(x\), the difference changes by \(-x\).

\[ dp[p][q][d] \to dp[p][q+1][d-x] \]

This applies only when \(q < Q\).

Speedup Using Range Sums

The purchase price \(x\) ranges over \(L \leq x \leq R\).

Although simply trying all values of \(x\) is already quite small given the constraints, the code uses prefix sums to batch the transitions.

For example, when Takahashi buys, if the destination difference is \(j\), then the source indices are:

\[ j-R, j-R+1, \dots, j-L \]

The sum of DP values over this range is computed in \(O(1)\) using prefix sums.

Similarly, when Aoki buys, if the destination difference is \(j\), then the source indices are:

\[ j+L, j+L+1, \dots, j+R \]

After processing all shops, the desired answer is:

\[ dp[P][Q][0] \]

In the code, a difference of \(0\) corresponds to index OFF, so we output:

dp[TARGET][OFF]

Here, TARGET is the index corresponding to \((P,Q)\).

Complexity

Let the length of the possible range of differences be:

\[ D = 20(P+Q)+1 \]

The number of states is:

\[ (P+1)(Q+1)D \]

Since we process all \(N\) shops via DP for each update:

• Time complexity: \(O\left(MN(P+1)(Q+1)D\right)\)
• Space complexity: \(O\left((P+1)(Q+1)D\right)\)

Given the constraints \(P,Q \leq 3\), \(D \leq 121\), and \(NM \leq 2000\), this is sufficiently fast.

Implementation Notes

• Since the difference \(S_T-S_A\) can be negative, we shift by OFF = 20 * Q to manage it in an array.
• To simplify DP indexing, the code flattens \((p,q)\) into a single dimension:

  index = p * (Q + 1) + q

• For each shop, we first copy the current DP into ndp to account for the “nobody buys” case.

• For transitions where Takahashi or Aoki buys, the sum over the price range \([L,R]\) is computed using prefix sums.

• The answer is obtained by recomputing the DP from scratch right after each update is applied. Since the constraint guarantees \(NM \leq 2000\), this approach is fast enough.

  Source Code

import sys

MOD = 998244353

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    P = next(it)
    Q = next(it)
    M = next(it)

    ranges = []
    for _ in range(N):
        l = next(it)
        r = next(it)
        ranges.append((l, r))

    Q1 = Q + 1
    P1 = P + 1
    SZ = P1 * Q1

    OFF = 20 * Q
    D = 20 * (P + Q) + 1
    TARGET = P * Q1 + Q

    def calc():
        dp = [[0] * D for _ in range(SZ)]
        dp[0][OFF] = 1

        for l, r in ranges:
            ndp = [arr[:] for arr in dp]

            for p in range(P1):
                base = p * Q1
                for q in range(Q1):
                    if p == P and q == Q:
                        continue

                    arr = dp[base + q]

                    pref = [0] * (D + 1)
                    s = 0
                    for i in range(D):
                        s += arr[i]
                        pref[i + 1] = s

                    if s == 0:
                        continue

                    if p < P:
                        dest = ndp[base + Q1 + q]
                        for j in range(l, D):
                            left = j - r
                            if left < 0:
                                left = 0
                            dest[j] += pref[j - l + 1] - pref[left]

                    if q < Q:
                        dest = ndp[base + q + 1]
                        end = D - l
                        for j in range(end):
                            right = j + r + 1
                            if right > D:
                                right = D
                            dest[j] += pref[right] - pref[j + l]

            for arr in ndp:
                for i in range(D):
                    if arr[i] >= MOD:
                        arr[i] %= MOD

            dp = ndp

        return dp[TARGET][OFF] % MOD

    ans = []
    for _ in range(M):
        x = next(it) - 1
        a = next(it)
        b = next(it)
        ranges[x] = (a, b)
        ans.append(str(calc()))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.