1009. 息息壤壤武陵的管道

题目描述

管理员已经厌烦了“自由探索塔卫二”的日子，再这样无聊下去，祂就要变成只会咕咕嘎嘎的凑企鹅了！

所以祂打算找点事情做——在武陵城内拉息壤管道做走廊！武陵城井然有序，中心城区可以视作由 $n\times m$ 个路口组成的点阵以及连接在相邻路口之间的街道组成，左上角的路口标号为 $(0,0)$，右下角的路口标号为 $(n-1,m-1)$，每个路口放置了一个管道桥（即每个路口可以视作一个节点），为了不影响居民的房子，每条息壤管道必须连在相邻的管道桥之间，且相邻的管道桥之间只能连接至多一条管道（即只能在相邻节点之间连至多一条无向边），候选管道的类型和标号遵循以下规则：

• 若为纵向，即连接在 $(x,y)$ , $(x+1,y)$ 两个路口之间，类型 $tp$ 为 $0$，标号为 $(x,y)$；
• 若为横向，即连接在 $(x,y)$ , $(x,y+1)$ 两个路口之间，类型 $tp$ 为 $1$，标号为 $(x,y)$；
• 注意不同类型的候选管道可能有相同标号。

管道连接后，会产生美观度 $w_{tp,x,y}$ ，当然，如果管理员不满意，美观度会是负的。同时由于地形等原因，每个候选管道存在限制 $r_{tp,x,y}$ ，有的不会受影响（即可以连接也可以不连接），有的必须不被连接，有的必须被连接。同时，祂认为每个管道桥都连接了偶数个管道（即每个节点要连偶数条无向边）才能算合法方案。为了锻炼陈千语，管理员让陈千语来帮祂计算合法方案的美观度，然而陈千语总是习惯性地按错计算器，因此她会按照一种奇怪的规则计算方案的美观度。 按照以下规则计算得到的值，即为该合法方案的最终美观度 ：

• 初始化计数器 $tot = 0$；
• 对于 $x$ 坐标相同的纵向管道（ $tp$ 为 $0$ 且 $x$ 相同），她从左边开始，依次向右检查，遇到第一条被连接的管道，给 $tot$ 加上它的美观度，遇到第二条被连接的管道，给 $tot$ 减去它的美观度，遇到第三条被连接的管道，给 $tot$ 加上它的美观度……以此类推；
• 即对于所有 $0 \le x \le n-2$，有 $tp=0$ ，标号 $(x,i_0),(x,i_1),\cdots,(x,i_{k-1})$ 的边被连接，且 $0\le i_0<i_1<\cdots< i_{k-1} < m$ , 计算 $tot_{V,x} = \sum_{j=0}^{k-1}(-1)^j w_{0,x,i_j}$；
• 对于 $y$ 坐标相同的横向管道（ $tp$ 为 $1$ 且 $y$ 相同），她从上边开始，依次向下检查，遇到第一条被连接的管道，给 $tot$ 加上它的美观度，遇到第二条被连接的管道，给 $tot$ 减去它的美观度，遇到第三条被连接的管道，给 $tot$ 加上它的美观度……以此类推；
• 即对于所有 $0 \le y \le m-2$，有 $tp=1$ ，标号 $(i_0,y),(i_1,y),\cdots,(i_{k-1},y)$ 的边被连接，且 $0\le i_0<i_1<\cdots< i_{k-1}< n$ , 计算 $tot_{H,y} = \sum_{j=0}^{k-1}(-1)^j w_{1,i_j,y}$；
• $tot = \sum_{x=0}^{n-2}tot_{V,x}+\sum_{y=0}^{m-2}tot_{H,y}$；
• 计算出的 $tot$ 即为这个合法方案的美观度。

管理员希望知道合法方案有多少种，以及所有合法方案的美观度之和是多少。两个合法方案不同当且仅当存在某一管道的连接情况不相同，同时空集（不连接任何管道）也算一种方案。且由于天气变动，接下来的 $q$ 天里，每一天都会有一条管道对应的美观度或限制发生变化（有可能变化前后相同），且该变化是持续的。第 $0,1,2,\cdots,q$ 天里，你都要回答管理员的疑问。

输入格式

每个测试文件包含多组测试数据。

第一行包含一个整数 $T$（$1 \le T \le 10$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含 $3$ 个整数 $n$ , $m$ , $q$ ，分别表示纵向路口数，横向路口数，变动次数，$n,m \ge 2$ ，$n \times m \le 10^5$ , $q \le 10^5$ ；
• 接下来 $n-1$ 行，每行 $m$ 个整数 ，第 $i+1$ 行第 $j+1$ 个数表示放置每个纵向管道的美观度 $w_{0,i,j}$ ；
• 接下来 $n$ 行，每行 $m-1$ 个整数 ，第 $i+1$ 行第 $j+1$ 个数表示放置每个横向管道的美观度 $w_{1,i,j}$ ；
• 美观度均在 $[-10^{10},10^{10}]$ 范围内；
• 接下来 $n-1$ 行，每行 $m$ 个整数 ，第 $i+1$ 行第 $j+1$ 个数表示放置每个纵向管道的限制 $r_{0,i,j}$ ；
• 接下来 $n$ 行，每行 $m-1$ 个整数 ，第 $i+1$ 行第 $j+1$ 个数表示放置每个横向管道的限制 $r_{1,i,j}$ ；
• 限制均在 $\{0,1,2\}$ 范围内，$0$ 表示任意（可以连接也可以不连接），$1$ 表示必须不被连接，$2$ 表示必须被连接；
• 接下来 $q$ 行，每行 $5$ 个整数 $op$ , $tp$ , $x$ , $y$ , $z$；
• $op,tp$ 均在 $\{0,1\}$ 范围内；
• 当 $tp$ 为 $0$ 时，表示选取纵向管道，$0 \le x \le n - 2$ ， $0 \le y \le m - 1$；
• 当 $tp$ 为 $1$ 时，表示选取横向管道，$0 \le x \le n - 1$ ， $0 \le y \le m - 2$；
• 当 $op$ 为 $0$ 时， $-10^{10} \le z \le 10^{10}$ ，表示令 $w_{tp,x,y}=z$；
• 当 $op$ 为 $1$ 时， $z \in \{0,1,2\}$ ，意义同上，表示令 $r_{tp,x,y}=z$；

数据保证 $\sum n \times m \leq 4 \times 10^5$ , $\sum q \leq 4 \times 10^5$。

输出格式

对于每组测试样例，第一次变动前和每一次变动后，每行给出两个整数 $ways$ , $sum$ ，分别表示合法方案数以及合法方案的美观度之和，用一个空格间隔，共输出 $q+1$ 行，对 $998244353$ 取模（输出 $[0,998244352]$ 之间的非负整数）

样例输入

5
2 2 0
0 0
0
0
0 0
0
0
2 2 2
2 0
1
1
2 2
0
0
0 1 1 0 0
1 0 0 0 0
2 3 1
2 0 1
4 2
3 2
2 0 0
2 0
0 0
0 1 1 0 0
2 3 3
2 3 2
2 4
1 3
2 2 1
0 0
0 1
0 0 0 1 0
0 1 0 1 1
1 1 1 1 2
2 2 0
-9999990910 -9999985805
-9999995425
-9999988339
0 0
0
2

样例输出

2 0
1 2
1 3
1 3
2 5
2 11
1 0
1 3
1 3
0 0
1 998232162

提示

对于第 $3$ 个样例：


第一次变动前，合法的方案有两个：

• 第一种是选择左边正方形对应的 $4$ 条管道：
  • 纵向管道为标号 $(0,0)$ 与 $(0,1)$，同一 $x$ 坐标依次加减计算得 $w_{0,0,0} - w_{0,0,1} = 2 - 0 = 2$；
  • 横向管道为标号 $(0,0)$ 与 $(1,0)$，同一 $y$ 坐标依次加减计算得 $w_{1,0,0} - w_{1,1,0} = 4 - 3 = 1$；
  • 该方案的美观度为 $2 + 1 = 3$。
• 第二种是选择最外圈对应的 $6$ 条管道：
  • 纵向管道为标号 $(0,0)$ 与 $(0,2)$，计算得 $2 - 1 = 1$；
  • 横向管道中，$y=0$ 的有 $(0,0)$ 与 $(1,0)$，计算得 $4 - 3 = 1$；$y=1$ 的有 $(0,1)$ 与 $(1,1)$，计算得 $2 - 2 = 0$；
  • 该方案的美观度为 $1 + 1 + 0 = 2$。
• 故初始合法方案数为 $2$，美观度之和为 $3 + 2 = 5$。

第一次变动后： 标号为 $(1,0)$ 的横向管道的美观度 $w_{1,1,0}$ 被修改为了 $0$。

• 第一种方案的美观度变为 $(2 - 0) + (4 - 0) = 6$；
• 第二种方案的美观度变为 $(2 - 1) + (4 - 0) + (2 - 2) = 5$；
• 故变动后合法方案数仍为 $2$，美观度之和变为 $6 + 5 = 11$。

来源：2026杭电多校-测试专用（杭电第1场-内测） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1009