难绷，考场上没调出来，调出来似乎就可以获得更加好看的545分了。

首先我们考虑哈希，然后因为今天已经写了一车哈希了，所以我们不考虑哈希。

我们考虑 $manacher$ ，由于我不会二维 $manacher$ ，我们考虑还是用一维的来做。

我们每行做马拉车，每列做马拉车，处理出来以每个数为中心往左右和上下最多扩展到哪里。

然后 $O(n^3)$ 就是再去枚举中心点，往外扩展。我们注意到 N 老师的数据不会太强，就直接这样做就对了。

但是我们要追求正确的复杂度，于是我们可以二分最远扩展的位置，然后使用 $ST$ 表判断是否合法。

然后空间就爆炸了。

然后我们的 $ST$ 表开成 $short$ 就行了。