Overview

This problem asks us to find the total number of plans where Takahashi selects \(P\) shops and Aoki selects \(Q\) shops from \(N\) shops to make purchases, such that the total amounts spent by both are equal. For each query, the purchasable price range \([L_i, R_i]\) of a shop is updated. By leveraging the constraints \(N \times M \le 2000\), \(P, Q \le 3\), and the very small maximum price of \(20\), we can solve this efficiently using dynamic programming (DP).

Analysis

1. Focus on the small state space

The key to this problem is that each parameter is very small. - The number of shops where Takahashi and Aoki make purchases, \(P, Q\), is at most \(3\). - The prices \(L_i, R_i\) at each shop are at most \(20\). - Therefore, the maximum total amount for one person is \(3 \times 20 = 60\).

The condition that both people’s total amounts are equal can be rephrased as ”(Takahashi’s total) - (Aoki’s total) = 0”. The range of this difference is only \(121\) values, from \(-60\) to \(60\).

2. Complexity estimation

For the number of queries \(M\) and the number of shops \(N\), there is a special constraint \(N \times M \le 2000\). This suggests that “even if we recompute the DP from scratch over all shops for each query, it will fit within the time limit.” The computation per single DP run is approximately \(O(N \times P \times Q \times (\text{range of price difference}))\). Even in the worst case, this is about \(2000 \times 3 \times 3 \times 121 \approx 2.1 \times 10^6\) operations. Since the total processing across all queries is on the order of \(N \times M\) rather than doing this \(M\) times independently, it comfortably fits within the time limit.

Algorithm

Definition of the Dynamic Programming

We perform DP with the following states: dp[p][q][diff]: - \(p\): the number of shops where Takahashi has made purchases (\(0 \le p \le P\)) - \(q\): the number of shops where Aoki has made purchases (\(0 \le q \le Q\)) - \(diff\): the current difference in total amounts (Takahashi - Aoki). To handle negative values, we add an offset (\(60\)) and manage it in the range \(0 \sim 120\).

Transitions

For each shop \(i\), there are the following 3 choices:

1. Nobody makes a purchase
   • next_dp[p][q][diff] += dp[p][q][diff]
2. Takahashi makes a purchase
   • Choose a price \(v \in [L_i, R_i]\).
   • next_dp[p+1][q][diff + v] += dp[p][q][diff]
3. Aoki makes a purchase
   • Choose a price \(v \in [L_i, R_i]\).
   • next_dp[p][q+1][diff - v] += dp[p][q][diff]

Optimization using prefix sums

Naively looping over “choosing a price \(v \in [L_i, R_i]\)” increases the computation, but by precomputing prefix sums over diff for dp[p][q], we can perform the range \([L_i, R_i]\) addition in \(O(1)\).

For example, next_dp[p+1][q][s] after Takahashi makes a purchase equals the sum of all values in the previous dp[p][q] where the difference is in the range from s - R[i] to s - L[i].

Complexity

• Time complexity: \(O(M \cdot N \cdot P \cdot Q \cdot S)\)
  • Here \(S\) is the range of the total price difference (approximately \(120\)).
  • Since \(N \times M \le 2000\), the total number of operations across all queries is about \(4 \times 10^6\), which is fast.
• Space complexity: \(O(P \cdot Q \cdot S)\)
  • By reusing (inlining) the DP table, we can implement it with memory independent of the number of shops \(N\).

Implementation Notes

• Negative indices: To prevent diff from becoming negative, we add OFFSET = 60 when managing it.

• Use of prefix sums: Instead of trying all prices within the range, we use prefix sums to speed up the inner loop.

• Initialization: At the start of each query, initialize the DP table to 0 and start from dp[0][0][OFFSET] = 1 (the state where nobody has purchased anything).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

/**
 * Problem: Equal Shopping
 * We have N shops, each with a range [Li, Ri].
 * Takahashi shops at exactly P shops, Aoki at exactly Q shops.
 * No same shop for both.
 * Total Takahashi sum = Total Aoki sum.
 * We need to count the number of such plans after each of M updates.
 * 
 * Constraints:
 * N <= 2000, P <= 3, Q <= 3, M <= 1000, N * M <= 2000.
 * Li, Ri <= 20.
 * 
 * DP state: dp[p][q][s]
 * p: number of shops Takahashi has used (0 to P)
 * q: number of shops Aoki has used (0 to Q)
 * s: current sum difference (Takahashi - Aoki), offset by 60 to handle negative values.
 * Max sum for each is 3 * 20 = 60. Max difference is 60.
 * The difference s ranges from -60 to 60, offset to 0 to 120.
 */

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, P, Q, M;
    if (!(cin >> N >> P >> Q >> M)) return 0;

    // Current ranges for each shop
    vector<int> L(N + 1), R(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> L[i] >> R[i];
    }

    const int MOD = 998244353;
    const int OFFSET = 60;
    const int MAX_S = 120;

    // Static DP tables to avoid re-allocation and keep memory usage low
    static int dp[4][4][121];
    static int next_dp[4][4][121];
    static int S[122];

    // Process M updates
    for (int j = 0; j < M; ++j) {
        int X, A, B;
        cin >> X >> A >> B;
        L[X] = A;
        R[X] = B;

        // Reset the DP table for the current configuration of shops
        memset(dp, 0, sizeof(dp));
        dp[0][0][OFFSET] = 1;

        // Dynamic Programming over all shops
        for (int i = 1; i <= N; ++i) {
            // next_dp[p][q][s] starts as dp[p][q][s] (case where no one shops at shop i)
            memcpy(next_dp, dp, sizeof(dp));

            for (int p = 0; p <= P; ++p) {
                for (int q = 0; q <= Q; ++q) {
                    // Optimization: Skip states that have no possible plans
                    bool all_zero = true;
                    for (int s = 0; s <= MAX_S; ++s) {
                        if (dp[p][q][s] != 0) {
                            all_zero = false;
                            break;
                        }
                    }
                    if (all_zero) continue;

                    // Compute prefix sums of dp[p][q][s] for range queries on sum difference
                    S[0] = 0;
                    for (int s = 0; s <= MAX_S; ++s) {
                        S[s + 1] = (S[s] + dp[p][q][s]) % MOD;
                    }

                    // Case: Takahashi shops at shop i
                    if (p + 1 <= P) {
                        for (int s = 0; s <= MAX_S; ++s) {
                            // s_new = s_old + v  =>  s_old = s_new - v
                            // v in [L[i], R[i]]  =>  s_old in [s - R[i], s - L[i]]
                            int low = s - R[i];
                            int high = s - L[i];
                            if (high < 0) continue;
                            if (low < 0) low = 0;
                            if (low <= high) {
                                int ways = (S[high + 1] - S[low] + MOD) % MOD;
                                next_dp[p + 1][q][s] = (next_dp[p + 1][q][s] + ways) % MOD;
                            }
                        }
                    }

                    // Case: Aoki shops at shop i
                    if (q + 1 <= Q) {
                        for (int s = 0; s <= MAX_S; ++s) {
                            // s_new = s_old - v  =>  s_old = s_new + v
                            // v in [L[i], R[i]]  =>  s_old in [s + L[i], s + R[i]]
                            int low = s + L[i];
                            int high = s + R[i];
                            if (low > MAX_S) continue;
                            if (high > MAX_S) high = MAX_S;
                            if (low <= high) {
                                int ways = (S[high + 1] - S[low] + MOD) % MOD;
                                next_dp[p][q + 1][s] = (next_dp[p][q + 1][s] + ways) % MOD;
                            }
                        }
                    }
                }
            }
            // Move updated DP state to current DP
            memcpy(dp, next_dp, sizeof(dp));
        }
        // Result is the number of plans where Takahashi used P shops, Aoki used Q shops, and sums were equal (diff=0).
        cout << dp[P][Q][OFFSET] << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3-flash-thinking.