#P13318. [2025年队测]黎明

    ID: 12502 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-欧拉示性数树状数组离散化离线预收集坐标增量维护

[2025年队测]黎明

题目描述

给出一个 n×mn\times m 的矩阵,矩阵每个位置都是一个整数,记第 ii 行第 jj 列的值为 ai,ja_{i, j}。

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

维护 qq 次操作,操作有两类:

  • add x,将矩阵中所有的值加 xx,即 ∀i,j,ai,j←ai,j+x\forall i, j, a_{i, j}\leftarrow a_{i, j}+x;

  • set x y z,将矩阵中 ax,ya_{x, y} 的值赋值为 zz,即 ax,y←za_{x, y}\leftarrow z。

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

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

  • 保证在任意时刻,不在边界上的位置,一定存在一个与它连通的位置的值严格小于它的值。

  • 即 ∀2≤i≤n−1,2≤j≤m−1\forall 2\leq i\leq n-1, 2\leq j\leq m-1,∃x,y,s.t.∣x−i∣+∣y−j∣=1,ax,y<ai,j\exists x, y,s.t. |x-i|+|y-j|=1, a_{x, y}<a_{i, j}。

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

输入格式

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

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

接下来 nn 行,每行 mm 个整数,描述初始时的矩阵。

接下来 qq 行,每行一个操作,形式同题面。

输出格式

输出 qq 行,每行一个整数,第 ii 行表示经过前 ii 次操作后矩阵的值。

样例

样例输入 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

5
1
0
0
0
0
2
4

样例 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 与子任务 11 的限制一致,

  • ex_daybreak3 与子任务 44 的限制一致,

  • ex_daybreak4 与子任务 55 的限制一致,

时空限制与数据范围

2s, 256MB

对于所有的数据:

  • $1\leq n,m\leq 1000, n\times m\leq 3\times 10^{5}, 1\leq q\leq 10^{5}$,

  • ∀i,j,∣ai,j∣≤109\forall i, j,|a_{i, j}|\leq 10^{9},

  • 对于 add x 操作,∣x∣≤109|x|\leq 10^{9},

  • 对于 set x y z 操作,1≤x≤n,1≤y≤m,∣z∣≤10151\leq x\leq n, 1\leq y\leq m, |z|\leq 10^{15}

子任务编号 n,m≤n,m\leq q≤q\leq 特殊性质 分值
11 100100 无 5
22 10001000 10510^{5} A 10
33 B
44 C 20
55 200200 3×1043\times 10^{4} D
66 10001000 10510^{5} 无 35

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

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

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

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