2020.10.17 T3 pig

发表于 2020-10-18 更新于 2023-12-07 分类于测试

题目

小七养了很多头猪，它们分布在 $n$ 行 $m$ 列中，其中第 $i$ 行第 $j$ 列的猪圈养的是第 $w_{i,j}$ 种猪。小七有时会选择一个子矩形范围内的猪圈进行巡视，如果该子矩形包含 $i $行 $j $列 $(1 ≤ i ≤ n, 1 ≤ j ≤ m)$，且子矩形内含有的猪种类编号最大值减去编号最小值恰好为 $i × j-1$ ，则小七会获得 $i × j$ 的愉悦值。

小七想知道，如果他将每个可能的子矩形都巡视一次，总共能获得多少愉悦值呢？你只需要输出答案对 $998244353$ 取模的结果。

分析

考虑判定权值在区间 $[l,r]$ 内的所有数所在的格子是否形成了一个矩形，记这些格子的颜色为黑色，其它的格子颜色为白色。

考虑所有的 $(n + 1) × (m + 1)$ 个 $2 × 2$ 的小正方形 (部分超出边界也算)，则所有黑色格子形成一个矩形，当且仅当恰好有 $4$ 个小正方形内部有 $1$ 个黑色格子，并且没有任何一个小正方形内部有 $3$ 个黑色格子。

从小到大枚举 $r$ ，对每个 $l ≤ r$ ，记 $f(l)$ 表示染黑权值在 $[l,r]$ 内的格子后，有多少小正方形内部有 $1$ 个或 $3$ 个黑色格子。

可以发现有 $f(l) ≥ 4, f(r) = 4 $，于是只需要对每个 $l$ 维护 $f(l)$ 最小值，最小值的数目和取得最小值的所有 $l$ 之和。

每次 $r$ 增加 $1$ 时，会影响到周边的 $4 $个 $2×2$ 的小正方形，在线段树上修改即可。

时间复杂度 $O(nm log nm)$ ，期望得分 $100$ 分。