ヒント → https://atcoder.jp/contests/arc190/editorial/11715

問題文では「パス」は \((1,1)\) で始まり \((H,W)\) で終わるものだけを指して定義していますが，解説では任意の \(2\) 点間の「パス」や「\(f(P)\)」を同様の意味で使います．

[1] 解法

次の \(2\) つの dp テーブルを用意します．

• \(\mathrm{dp}_1[h][w]\) : \((1,1)\) から \((h,w)\) へのパス \(P\) に対する \(f(P)\) の総和．
• \(\mathrm{dp}_2[h][w]\) : \((h,w)\) から \((H,W)\) へのパス \(P\) に対する \(f(P)\) の総和．

高橋君がマス \((a,b)\) に居るとき，

• \(1\leq h\leq a\) に対する \(\mathrm{dp}_1[h][w]\)
• \(a\leq h\leq H\) に対する \(\mathrm{dp}_2[h][w]\)

が正しく計算された状態を保持するようにします．これはクエリごとに第 \(a\) 行に対する再計算を行えばよく，クエリごとに \(O(W)\) 時間で行えます．

これらの dp テーブルが保持できていれば，答の差分計算が \(O(1)\) 時間で簡単に行えます．あるいは \(a\) 行目から \(a+1\) 行目に移動する列を考えて \(\mathrm{ANS}=\sum_{w} \mathrm{dp}_1[a][w] \mathrm{dp}_2[a+1][w]\) などの計算により \(O(W)\) 時間で再計算することも可能です．

以上により本問題は \(O(HW+WQ)\) 時間で解くことができます．\(H\leq W\) ならば行・列を入れ替えて全く同じ方法をとることで，\(O(HW+\min(H,W)Q)\) 時間で本問題を解くことができます．

• 解答例：https://atcoder.jp/contests/arc190/submissions/61518720