概要

各店を「使わない・高橋が使う・青木が使う」の3択で処理する動的計画法（DP）を作り、さらに更新クエリごとに「その店の寄与を外して付け直す」ことで高速に答えを出す問題です。
ポイントは、\(P,Q \le 3\)・金額上限が20なので、合計差分の範囲が小さく抑えられることです。

考察

まず、条件「高橋の合計金額 = 青木の合計金額」は、差分 [ d = (\text{高橋合計}) - (\text{青木合計}) ] を持てば「最終的に \(d=0\)」と言い換えられます。

1. 基本DP

店を左から見ていくとき、状態を - 高橋が使った店数 \(p\) - 青木が使った店数 \(q\) - 差分 \(d\)

で持てます。
各店 \((L_i,R_i)\) について遷移は3通りです。

1. 誰も使わない：状態そのまま
2. 高橋が使う：\(p \to p+1,\ d \to d+v\ (L_i \le v \le R_i)\)
3. 青木が使う：\(q \to q+1,\ d \to d-v\ (L_i \le v \le R_i)\)

最終的な答えは \(\mathrm{dp}[P][Q][0]\) です。

2. 素朴に毎クエリ再計算すると遅い

クエリごとに全店でDPを最初から作り直すと、だいたい [ O(M \cdot N \cdot P \cdot Q \cdot D \cdot 20) ] 程度かかります。制約上ギリギリ〜厳しめです。

3. 「1店分の作用」を足す・引く

このコードの核心はここです。

1店の処理を線形変換 \(F_i\) と見ると、全体は [ \text{coeff} = F_N \circ \cdots \circ F_1 (\text{初期ベクトル}) ] です。
クエリで店 \(x\) の範囲だけ変わるなら、 - 旧 \(F_x\) を逆操作で外す - 新 \(F_x\) を適用し直す

だけで済みます。

なぜ逆操作できるのか

1店の適用は [ \text{new} = \text{old} + T(\text{old}) ] の形（「使わない」成分 + 「使う」成分）で、\(T\) は必ず \(p\) または \(q\) を1増やします。
つまり依存関係が「小さい \((p,q)\) から大きい \((p,q)\)」への一方向なので、
old[0][0] から順に復元できます（トポロジカル順の連立一次方程式の前進解法のイメージ）。

これにより unapply_store が実現でき、更新を高速化できます。

アルゴリズム

1. 差分範囲を固定する。
   \(P,Q \le 3\), 金額最大20なので
   [ d \in [-60,60] ] で十分。
2. coeff[p][q][d] を「現在の全店を反映した通り数」とする。
3. 初期状態 coeff[0][0][0]=1。
4. 全店について apply_store(L[i],R[i]) を順に実行して初期全体を作る。
5. 各クエリで
   • unapply_store(旧L[x],旧R[x])
   • 範囲更新
   • apply_store(新L[x],新R[x])
   • coeff[P][Q][0] を出力

apply_store は「その店を使わない」分を残すため nxt = coeff から始め、使う遷移を加算。
unapply_store は前述の順方向復元で old を再構成して coeff=old に戻します。

計算量

• 時間計算量:
  初期構築が \(O(N \cdot P \cdot Q \cdot D \cdot 20)\)、
  各クエリが unapply + apply で同程度
  [ O\big((N+M)\cdot P\cdot Q\cdot D\cdot 20\big) ] （ここで \(D=121,\ P,Q\le3\) なので十分高速）
• 空間計算量:
  [ O(P\cdot Q\cdot D) ]

実装のポイント

• 差分配列は負数を扱うので、didx(d)=d-DMIN のようなオフセットを使う。

• unapply_store では old を p=0..P, q=0..Q の順で埋めることが重要（依存が小さい側だけだから）。

• mod計算で負にならないように都度補正する。

• コード中の sign 引数は未使用だが、ロジック上は apply/unapply を明確に分けて実装できている。

  ソースコード

#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;
}

---

この解説は gpt-5.3-codex によって生成されました。