D

DP RMQ
每次RMQ预处理出每条对角线的color-1的最小值
更新的时候枚举距离,即枚举对角线,注意在以下情况对角线距离才表示两点间距离

2
212
21X12 …
212
2

复杂度 $O(pnlog(n) + mn^2)$

分块暴力 (题解做法)
如果$cnt_icnt_{i-1} < n*m$直接暴力转移,否则做一次bfs

暴力转移的复杂度为$O(nm)$,最多有$\sqrt{nm}$次
bfs复杂度为$O(\sqrt{nm})$,最多有$nm$次

复杂度 $O(nm\sqrt{nm})$

E

在一由0,1,2,3构成的方阵中选择一个小方阵(边长为奇数)
求方阵的两条对角线上或者方阵的十字上的所有数字的最大乘积

暴力

首先预处理出每个点在八个方向上的最远扩展(非0),然后再预处理四个方向的前缀和(用log表示)
这样我们暴力枚举中心,再考虑两种扩展方式,求一个最大值。