AT_arc190_c [ARC190C] Basic Grid Problem with Updates

给定一个 $H \times W$ 的网格。从上往下第 $h$ 行、从左往右第 $w$ 列的单元格记为 $(h, w)$，其中存储了一个非负整数 $A_{h,w}$。 高桥君初始位于单元格 $(sh, sw)$，接下来将进行 $Q$ 次修改操作。第 $i$ 次修改由字符 $d_i$（取值为 `L`、`R`、`U`、`D` 之一）和非负整数 $a_i$ 描述，具体操作如下： - 向 $d_i$ 方向移动 $1$ 格（`L` 为左，`R` 为右，`U` 为上，`D` 为下），将移动后的单元格 $(h, w)$ 中的 $A_{h,w}$ 修改为 $a_i$。 （保证每次移动操作合法） 每次修改后，请计算以下问题的答案： > 定义**路径** $P = ((h_1, w_1), \ldots, (h_M, w_M))$ 为满足以下条件的单元格序列： > - 起点 $(h_1, w_1) = (1, 1)$，终点 $(h_M, w_M) = (H, W)$，且 $M = H + W - 1$ > - 对于任意 $1 \leq i \leq M-1$，满足 $(h_{i+1}, w_{i+1}) = (h_i + 1, w_i)$ 或 $(h_{i+1}, w_{i+1}) = (h_i, w_i + 1)$ > > 所有可能的路径共有 $\binom{H + W - 2}{H - 1}$ 条。定义 $f(P) = \prod_{1 \leq i \leq M} A_{h_i, w_i}$，求所有路径 $P$ 的 $f(P)$ 之和模 $998244353$ 的结果。

输入格式如下： > $H$ $W$ > $A_{1,1}$ $\cdots$ $A_{1,W}$ > $\vdots$ > $A_{H,1}$ $\cdots$ $A_{H,W}$ > $Q$ > $sh$ $sw$ > $d_1$ $a_1$ > $\vdots$ > $d_Q$ $a_Q$

输出 $Q$ 行，每行对应每次修改后的答案。

### 约束条件 - $2 \leq H, W \leq 2 \times 10^5$ - $H \cdot W \leq 2 \times 10^5$ - $0 \leq A_{h,w} < 998244353$ - $1 \leq Q \leq 2 \times 10^5$ - $1 \leq sh \leq H$, $1 \leq sw \leq W$ - $0 \leq a_i < 998244353$ - 保证每次移动操作合法 ### 样例解释 1 - 初始时高桥君位于 $(2, 2)$。 - **第一次操作**（向上移动并修改 $A_{1,2}$ 为 $7$）： - $P=((1,1),(1,2),(1,3),(2,3))$: $f(P) = 1 \times 7 \times 3 \times 6 = 126$ - $P=((1,1),(1,2),(2,2),(2,3))$: $f(P) = 1 \times 7 \times 5 \times 6 = 210$ - $P=((1,1),(2,1),(2,2),(2,3))$: $f(P) = 1 \times 4 \times 5 \times 6 = 120$ - **第二次操作**（向右移动并修改 $A_{1,3}$ 为 $8$）： - $P=((1,1),(1,2),(1,3),(2,3))$: $f(P) = 1 \times 7 \times 8 \times 6 = 336$ - 其他路径的 $f(P)$ 保持不变（$210$ 和 $120$）。 - **第三次操作**（向左移动并修改 $A_{1,2}$ 为 $9$）： - $P=((1,1),(1,2),(1,3),(2,3))$: $f(P) = 1 \times 9 \times 8 \times 6 = 432$ - $P=((1,1),(1,2),(2,2),(2,3))$: $f(P) = 1 \times 9 \times 5 \times 6 = 270$ - $P=((1,1),(2,1),(2,2),(2,3))$: $f(P) = 1 \times 4 \times 5 \times 6 = 120$ 翻译由 DeepSeek R1 完成