涉及知识：
哈希、Manacher，没了。
做法：
题意非常清晰，无需赘述，直接讲做法。
看到对称想到 Manacher，不妨考虑将一维的 Manacher 略略扩展，考虑到类似于枚举中心的思路。我们只要对每一行都跑一次 Manacher 便可以达成这个要求。
考虑一维和二维的不同之处，在转移时我们原本所需要考虑的“相同的一对点”变成了“相同的两对线”，即上与下，左与右。想到这里就已经可以写出一份保证有正确性的代码了。
然而我们分析复杂度，每一次比较四条线是 \(O(n+m)\) 的，而每一行都跑一次 Manacher 是 \(O(nm)\) 的，加起来总共是 \(O(n^3)\) 的，显然无法通过此题。
我们考虑优化，发现其实 Manacher 已经没有什么好优化的地方了，于是优化比较的过程，发现比较连续序列是否相等可以用字符串哈希 \(O(1)\) 来做，但是值域偏大，数又多，容易冲突，考虑离散化，可以将值域降低到 \(10^6\) 的大小，比较安全，单哈希自然溢出直接通过。
哈希因为是二维，预处理时间复杂度 \(O(n m)\)，算上 Manacher 的 \(O(n m)\)，总复杂度 \(O(n m)\)。
注意：
首先是不要记录不合法的答案，记录方形半径的数组只会在 \(x\)、\(y\) 同为奇数或偶数时才有贡献，不用管。
其次是不要看成中心对称，虽然我觉得只有我会看成这个。
Code：
感觉我的码算比较短的了（码风不毒），注释写的还算详细，总之看得愉快！
#include <bits/extc++.h>
#define e_ putchar(' ')
#define en_ putchar('\n')
using uint = unsigned int; // 好像c++多少后就直接有这个不用定义了，但是想到dev会报错，所以还是定义了
using namespace std;
template <typename T> inline T in(T &n) {n = 0; char p = getchar();while(p < '-') p = getchar();
// bool f = p == '-' ? p = getchar() : 0;do n = (n << 1) + (n << 3) + (p ^ 48), p = getchar();while(isdigit(p));
// return n = f ? -n : n;return n;
}
template <typename T> inline void out(T x) {if(x < 0) putchar('-'), x = -x;if (x >= 10) out(x / 10);putchar(x % 10 + '0');
}
constexpr int N = 2000 + 100;
constexpr uint p = 1007;
uint wd[N][N], wr[N][N], pp[N], wl[N][N], wu[N][N];
int s[N][N], l[N][N], n, m;
long long ans;
vector<int> t;
inline void pre() { // 预处理哈希pp[0] = 1;for(int i = 1; i < N; i ++) pp[i] = pp[i - 1] * p;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++) wr[i][j] = s[i][j] + wr[i][j - 1] * p;for(int i = 1; i <= n; i ++)for(int j = m; j >= 1; j --) wl[i][j] = s[i][j] + wl[i][j + 1] * p;for(int j = 1; j <= m; j ++)for(int i = 1; i <= n; i ++)wd[i][j] = wd[i - 1][j] * p + s[i][j];for(int j = 1; j <= m; j ++)for(int i = n; i >= 1; i --)wu[i][j] = wu[i + 1][j] * p + s[i][j];
}
inline bool check(int i, int j, int len) { // 同样比较丑陋的比较if(i - len < 1 or i + len > n or j + len > m or j - len < 1) return 0;uint a = wr[i - len][j + len] - wr[i - len][j - len - 1] * pp[len + len + 1],b = wr[i + len][j + len] - wr[i + len][j - len - 1] * pp[len + len + 1],c = wd[i + len][j + len] - wd[i - len - 1][j + len] * pp[len + len + 1],d = wd[i + len][j - len] - wd[i - len - 1][j - len] * pp[len + len + 1],e = wl[i - len][j - len] - wl[i - len][j + len + 1] * pp[len + len + 1],f = wu[i - len][j + len] - wu[i + len + 1][j + len] * pp[len + len + 1];if(a != b or c != d or a != e or f != c) return 0;return 1;
}
inline void mnc(int *l, int *s, int c) { // 马拉车for(int i = 1, o = 0, r = -1; i <= m; i ++) {l[i] = i <= r ? min(r - i, l[o * 2 - i]) : 1;while(check(c, i, l[i])) l[i] ++;if(l[i] + i - 1 > r) r = l[i] + i - 1, o = i;}
}
signed main() {in(n), in(m);for(int i = 1; i <= n * 2 + 2; i ++) { // 一个比较丑陋的读入for(int j = 1; j <= m * 2 + 1; j ++) s[i][j] = 1000001;i ++;if(i == n * 2 + 2) break;for(int j = 1; j <= m * 2; j ++) {s[i][j] = 1000001;in(s[i][++j]);t.push_back(s[i][j]);}s[i][m * 2 + 1] = 1000001;}n = n * 2 + 1;m = m * 2 + 1;sort(t.begin(), t.end()); // 离散化t.erase(unique(t.begin(), t.end()), t.end());for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)if(!(i & 1) and !(j & 1)) s[i][j] = lower_bound(t.begin(), t.end(), s[i][j]) - t.begin() + 1;pre(); // 预处理哈希（具体见上）for(int i = 1; i <= n; i ++) // 给每行跑一次马拉车mnc(l[i], s[i], i);for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)if((!(i & 1) and !(j & 1)) || ((i & 1) and (j & 1)))ans += (l[i][j]) / 2; // 统计答案out(ans), en_;
}