0分求调

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int maxn=2e3+10;
int a[maxn][maxn],c[maxn][maxn];
int p1[maxn][maxn],p2[maxn][maxn],pp[maxn],lr[maxn][maxn],ud[maxn][maxn];
int lg[maxn];
int f[maxn][13];
long long ans;
int n,m;
inline void solve(int opt,int id,int len,int p[][maxn])
{
	memset(pp,0,sizeof pp);
	int mid=0,r=0;
	for (int i=1;i<len;i++)
	{
		if (pp[i]<=r) pp[i]=min(pp[mid*2-i],r-i+1);
		else pp[i]=1;
		if (opt) while (c[id][i+pp[i]]==c[id][i-pp[i]]) pp[i]++;
		else while (c[i+pp[i]][id]==c[i-pp[i]][id]) pp[i]++;
		if (i+pp[i]-1>r)
		{
			r=i+pp[i]-1;
			mid=i;
		}
	}
	if (opt) for (int i=1;i<len;i++) p[id][i]=pp[i]-1; 
	else for (int i=1;i<len;i++) p[i][id]=pp[i]-1; 
}
inline int query(int l,int r,int len)
{
	if (l<=0||r>=len) return 0;
	int s=r-l+1;
	return min(f[l][lg[s]],f[r-(1<<lg[s])+1][lg[s]]);
}
inline void init_(int len)
{
	for (int j=1;j<=lg[len];j++)
	{
		for (int i=1;i+(1<<j)-1<=len;i++)
		{
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		} 
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	lg[1]=0;
	for (int i=2;i<=2040;i++) lg[i]=lg[i>>1]+1;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++) 
			cin>>a[i][j];
	for (int i=0;i<=2*n+2;i++) c[i][0]=-1;
	for (int i=0;i<=2*m+2;i++) c[0][i]=-1;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			c[i*2+2][j*2+2]=a[i][j];
	for (int i=0;i<=2*n+2;i++) c[i][2*m+2]=-2;
	for (int i=0;i<=2*m+2;i++) c[2*n+2][i]=-2;
	n=2*n+2,m=2*m+2;
	for (int i=1;i<n;i++) solve(1,i,m,p1);
	for (int i=1;i<m;i++) solve(0,i,n,p2);
	for (int i=1;i<n;i++)
	{
		memset(f,0,sizeof f);
		for (int j=1;j<m;j++)
		{
			f[j][0]=p2[i][j];
		}
		init_(m-1);
		for (int j=1;j<m;j++)
		{
			int l=0,r=m;
			while (l<r)
			{
				int mid=(l+r+1)>>1;
				if (query(j-mid+1,j+mid-1,m-1)>=mid) l=mid;
				else r=mid-1;
			}
			lr[i][j]=l;
		}
	}
	for (int i=1;i<m;i++)
	{
		memset(f,0,sizeof f);
		for (int j=1;j<n;j++)
		{
			f[j][0]=p1[j][i];
		}
		init_(n-1);
		for (int j=1;j<n;j++)
		{
			int l=1,r=n;
			while (l<r)
			{
				int mid=(l+r+1)>>1;
				if (query(j-mid+1,j+mid-1,n-1)>=mid) l=mid;
				else r=mid-1;
			}
			ud[j][i]=l;
		}
	}
	for (int i=1;i<n;i++)
	{
		for (int j=1;j<m;j++)
		{
			int x=min(lr[i][j],ud[i][j]);
			if (c[i][j]>0) ans+=(x+1)/2;
			else ans+=x/2;
		}
	}
	cout<<ans<<"\n";
	return 0;
}