P12561 [UTS 2024] Matrix

给定一个大小为 $n \times m$ 的矩阵，矩阵元素为 $a_{i,j}$。 我们定义以点 $(x,y)$ 为起点、大小为 $k$ 的**三角形**为：从 $(x,y)$ 出发，通过向上或向右移动不超过 $k-1$ 步所能到达的所有点的集合。 对于每个满足 $(k \le x \le n, 1 \le y \le m-k+1)$ 的点 $(x,y)$，需要求出以下两个值： - 以 $(x,y)$ 为起点的大小为 $k$ 的三角形中的最大值； - 该最大值在三角形中出现的次数。

第一行包含三个整数 $n$、$m$ 和 $k$ $(1 \le n,m \le 2\,000, 1 \le k \le \min(n,m))$ —— 分别表示矩阵的行数、列数和三角形的大小。 接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}$ $(0 \le a_{i,j} \le 10^6)$ —— 表示矩阵的元素。

输出两个大小为 $(n-k+1) \times (m-k+1)$ 的矩阵。 第一个矩阵的第 $(i,j)$ 个位置应包含以 $(i+k-1,j)$ 为起点的大小为 $k$ 的三角形中的最大值。 第二个矩阵的第 $(i,j)$ 个位置应包含该最大值在对应三角形中出现的次数。

- （$5$ 分）：$n,m \le 20$； - （$10$ 分）：$n,m \le 100$； - （$30$ 分）：$a_{i,j} \le 1$； - （$35$ 分）：$n,m \le 1\,000$； - （$20$ 分）：无额外限制。 翻译由 DeepSeek V3 完成