T4 黎明

(daybreak/2s/256MB)

题目背景

黎明前线。

不要停下脚步。

题目描述

给出一个 $n\times m$ 的矩阵，矩阵每个位置都是一个整数，记第 $i$ 行第 $j$ 列的值为 $a_{i, j}$。

定义矩阵的值为正整数连通块的数量，两个位置 $(x_1, y_1), (x_2, y_2)$ 连通当且仅当 $|x_1-x_2|+|y_1-y_2|=1$。

维护 $q$ 次操作，操作有两类：

add x，将矩阵中所有的值加 $x$，即 $\forall i, j, a_{i, j}\leftarrow a_{i, j}+x$；
set x y z，将矩阵中 $a_{x, y}$ 的值赋值为 $z$，即 $a_{x, y}\leftarrow z$。

你需要在每次操作后求出矩阵的值。

矩阵有一个重要的性质如下：

保证在任意时刻，不在边界上的位置，一定存在一个与它连通的位置的值严格小于它的值。
即 $\forall 2\leq i\leq n-1, 2\leq j\leq m-1$，$\exists x, y,s.t. |x-i|+|y-j|=1, a_{x, y}

本题采用子任务捆绑测试。

输入格式

第一行一个整数 $taskid$ ，表示子任务编号。 $taskid=0$ 表示样例。

接下来一行三个整数 $n,m, q$，表示矩阵的大小和操作次数。

接下来 $n$ 行，每行 $m$ 个整数，描述初始时的矩阵。

接下来 $q$ 行，每行一个操作，形式同题面。

输出格式

输出 $q$ 行，每行一个整数，第 $i$ 行表示经过前 $i$ 次操作后矩阵的值。

样例

样例输入 1

0
4 4 8
1 0 0 1
0 2 2 0
0 2 2 0
1 0 0 1
add 0
add -1
add -1
set 2 2 -1
set 3 3 -1
set 3 4 -1
add 1
add 1

样例输出 1

样例 1 解释

初始时，矩阵如下：

$$ \begin{matrix} 1, 0, 0, 1\\\\ 0, 2, 2, 0\\\\ 0, 2, 2, 0\\\\ 1, 0, 0, 1 \end{matrix} $$

进行一次 add -1：

$$ \begin{matrix} 0, -1, -1, 0\\\\ -1, 1, 1, -1\\\\ -1, 1, 1, -1\\\\ 0, -1, -1, 0 \end{matrix} $$

再进行一次 add -1：

$$ \begin{matrix} -1, -2, -2, -1\\\\ -2, 0, 0, -2\\\\ -2, 0, 0, -2\\\\ -1, -2, -2, -1 \end{matrix} $$

进行完所有的操作：

$$ \begin{matrix} 1, 0, 0, 1\\\\ 0,1, 2, 0\\\\ 0, 2, 1, 1\\\\ 1, 0, 0, 1 \end{matrix} $$

其余样例见下发文件。

ex_daybreak2 与子任务 $1$ 的限制一致，
ex_daybreak3 与子任务 $4$ 的限制一致，
ex_daybreak4 与子任务 $5$ 的限制一致，

时空限制与数据范围

2s, 256MB

对于所有的数据：

$1\leq n,m\leq 1000, n\times m\leq 3\times 10^{5}, 1\leq q\leq 10^{5} $,
$\forall i, j,|a_{i, j}|\leq 10^{9}$,
对于 add x 操作，$|x|\leq 10^{9}$,
对于 set x y z 操作，$1\leq x\leq n, 1\leq y\leq m, |z|\leq 10^{15}$

子任务编号	$n,m\leq $	$q\leq $	特殊性质	分值
$1$	$100$	$100$	无	5
$2$	$1000$	$10^{5}$	A	10
$3$	$1000$	$10^{5}$	B	10
$4$	$1000$	$10^{5}$	C	20
$5$	$200$	$3\times 10^{4}$	D	20
$6$	$1000$	$10^{5}$	无	35

特殊性质 A: 没有 add x 操作，

特殊性质 B: 没有 set x y z 操作，

特殊性质 C: 进行 add x 操作时，$x\geq 0$，

特殊性质 D: 任意时刻 $\forall i, j,|a_{i, j}|\leq 10^{5}$。

YY Online Judge

YYOJ

#2895. 20251007.4.黎明（daybreak）