典。

不难发现最短路的要求就是每次只能向右或者向下走。

如果一开始一点头绪都没有，可以先想一个非常暴力的动规。

钦定 $f_{i, j, k}$ 表示从 $(1, 1)$ 走向右或者向下走到 $(i, j)$，$k$ 这个值的最多出现次数；$g_{i, j, k}$ 同理，只不过从 $(n, n)$ 向左或向上走到 $(i, j)$。

转移：

$$f_{i, j, k} = \max(f_{i, j - 1, k}, f_{i - 1, j, k}) + [A_{i, j} = k]\\ g_{i, j, k} = \max(g_{i, j + 1, k}, g_{i + 1, j, k}) + [A_{i, j} = k]$$

最后每一个点的冗余度为 $f_{i, j, A_{i, j}} + g_{i, j, A_{i, j}} - 1$。

时间复杂度和空间复杂度都是 $O(n^4)$ 的，明显不能通过。

---

但是发现每一个点最多只会对一种值有影响，所以我们完全没必要存过多冗杂的信息。

于是可以对每一种不同的值分开讨论，假设当前我们只考虑 $v$ 这个值。

那么钦定 $z_{i, j}(A_{i, j} = v)$ 表示从 $(1, 1)$ 走向右或者向下走到 $(i, j)$，$v$ 这个值的最多出现次数（反向同理）。

转移可以写成：

$$z_{i, j} = \max_{x \le i\wedge y\le j\wedge A_{x, y} = v} z_{x, y} + 1$$

这就是一个二维偏序，每次找出 $(1, 1)\sim (i, j)$ 这个矩形中 $A_{x, y} = v$ 的 $z_{x, y}$ 的最大值。

那么就非常典了，我们把每种颜色的位置离线下来，按照 $x, y$ 升序排序，用树状数组维护前缀最大值即可。

每个点因为只会被操作 $O(1)$ 次，所以总时间复杂度 $O(n^2\log n)$。

:::success[code]

int main() noexcept{
	read (n);

	for (i32 i = 1; i <= n; i++) 
		for (i32 j = 1; j <= n; j++) {
			read (s[i][j]);
			G[s[i][j]].push_back ({i, j}); /*对于每种不同的颜色离线*/
		}
	
	for (i32 i = 1; i <= n * n; i++) {
		if (G[i].size ()) {
			std::sort (G[i].begin (), G[i].end ()); /*按照 x, y 升序排序*/
			for (auto it : G[i]) {
				i64 x = it.first, y = it.second;
				v[x][y] = Tr.ask (y) + 1;
				Tr.update (y, v[x][y]); /*二维偏序，树状数组维护前缀最大值*/
			}
			for (auto it : G[i]) Tr.Mem (it.second);
			std::sort (G[i].begin (), G[i].end (), [&] (auto a, auto b) noexcept {
				return a.first == b.first ? a.second > b.second : a.first > b.first;
			}); /*反着做一遍*/
	
			for (auto it : G[i]) {
				i64 x = it.first, y = it.second;
				z[x][y] = Tr.ask (n - y + 1) + 1;
				Tr.update (n - y + 1, z[x][y]); /*同理*/
			}
			for (auto it : G[i]) Tr.Mem (n - it.second + 1); /*不能全局清空，不然复杂度会退化到 $O(n^3)$*/
		}
	}
	
	for (i32 i = 1; i <= n; i++) 
		for (i32 j = 1; j <= n; j++) 
			tot[v[i][j] + z[i][j] - 1]++;/*求出每个点的冗余度*/
	
	for (i32 i = 1; i <= n * 2 - 1; i++)
		put (tot[i]); /*输出答案*/
    return 0;
}

:::