Description

Orez很喜欢搜集一些神秘的数据,并经常把它们排成一个矩阵进行研究。最近,Orez又得到了一些数据,并已经把它们排成了一个n行m列的矩阵。通过观察,Orez发现这些数据蕴涵了一个奇特的数,就是矩阵中上下对称且左右对称的正方形子矩阵的个数。 Orez自然很想知道这个数是多少,可是矩阵太大,无法去数。只能请你编个程序来计算出这个数。

Input

文件的第一行为两个整数n和m。接下来n行每行包含m个正整数,表示Orez得到的矩阵。

Output

文件中仅包含一个整数answer,表示矩阵中有answer个上下左右对称的正方形子矩阵。

Sample Input

5 5
4 2 4 4 4
3 1 4 4 3
3 5 3 3 3
3 1 5 3 3
4 2 1 2 4

Sample Output

27

数据范围
对于30%的数据 n,m≤100
对于100%的数据 n,m≤1000 ,矩阵中的数的大小≤109

题解:

  蒟蒻写了4h……(本来是想怂,但看到人家说gang了一晚上,然后默默关了网页自己去作了),还有,膜bzoj 1414榜上900B+400MS大佬。

   首先用manacher,双倍复制原数组,跑出$P_{0,i,j},P_{1,i,j}$,分别表示第i行j列的横着的和竖着的回文半径。

  显然只要求出每个位置的最大正方形边长答案就出来了。

  我们以每个位置$(i,j)$为坐标轴原点,显然,我们只要得到x,y轴上的回文半径即可。先讨论x非负轴。同时,对于每个位置我们可以观察发现,在x轴上的位置,应该满足其$x-p[1][i][x]+1<=j$。然后发现对于$(i,j+1)$是可以继承满足$(i,j)$的一部分点,而不能继承的只有$(i,j)$在x轴对应点,同时我们可能会有一部分新点加入$(i,j+1)$的集合点。(⊙v⊙)嗯,这不就是队列的时间关系嘛。

  然后怎么选取$(i,j)$所能得到的此时尽可能最大值边长呢。我们可以画个图,观察发现,我们在$(i,j)$点集的选取,只和最小值有关,所以当出现第一个不满足$x-p_{1,i,x}+1<=j$的点就没必要再在非负半轴上往后扫了。

  证明的话倒是挺简单的,就不多说了。

  以上一结合就得到了我们需要的数据结构,单调队列。

  那么对于x非正半轴以及y轴的情况也与x非负半轴的情况相同。时间复杂度$O(n^{2})$

  最后答案累加每个$(i,j)$奇偶性相同的位置即可。

Ps:可能是我打得蠢……都跑不过带$log$的……

代码:

  

 #include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
inline int read(){
int s=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') s=s*+(ch^),ch=getchar();
return s;
}
int n,m;
int Mar[][];
int p[][][];
inline void manacher(){
for(int i=;i<=*n+;i++){
int pos,mar=;
for(int j=;j<=*m+;j++){
if(mar>j) p[][i][j]=min(p[][i][pos*-j],mar-j-);
else p[][i][j]=;
while(Mar[i][j-p[][i][j]]==Mar[i][j+p[][i][j]]) p[][i][j]++;
if(mar<j+p[][i][j]-)
mar=j+p[][i][j]-,pos=j;
}
}
for(int i=;i<=*m+;i++){
int pos,mar=;
for(int j=;j<=*n+;j++){
if(mar>j) p[][i][j]=min(p[][i][pos*-j],mar-j-);
else p[][i][j]=;
while(Mar[j-p[][i][j]][i]==Mar[j+p[][i][j]][i]) p[][i][j]++;
if(mar<j+p[][i][j]-)
mar=j+p[][i][j]-,pos=j;
}
}
}
int que[],l,r;
int re[][];
int main(){
n=read(),m=read();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
Mar[i<<][j<<]=read();
for(int i=;i<=*n+;i++)
Mar[i][]=-,Mar[i][m+<<]=-;
for(int i=;i<=*m+;i++)
Mar[][i]=-,Mar[n+<<][i]=-;
manacher();
for(int i=;i<=*n;i++){
l=,r=;
for(int j=((i^)&)+,k=;j<=*m+;j+=){
while(k<=*m+&&k-p[][k][i]+<=j){
while(l<=r&&p[][que[r]][i]>=p[][k][i])
r--;
que[++r]=k;
k++;
}
while(l<=r&&que[l]<j)
l++;
re[i][j]=min(que[r]-j+,p[][que[l]][i]);
}
l=,r=;
for(int j=*m+-((i^)&),k=*m+;j>=;j-=){
while(k&&k+p[][k][i]->=j){
while(l<=r&&p[][que[r]][i]>=p[][k][i])
r--;
que[++r]=k--;
}
while(l<=r&&que[l]>j)
l++;
re[i][j]=min(min(j-que[r]+,p[][que[l]][i]),re[i][j]);
} }
for(int i=;i<=*m;i++){
l=,r=;
for(int j=+((i^)&),k=;j<=*n+;j+=){
while(k<=*n+&&k-p[][k][i]+<=j){
while(l<=r&&p[][que[r]][i]>=p[][k][i])
r--;
que[++r]=k;
k++;
}
while(l<=r&&que[l]<j)
l++;
re[j][i]=min(min(que[r]-j+,p[][que[l]][i]),re[j][i]);
}
l=,r=;
for(int j=*n+-((i^)&),k=*n+;j;j--){
while(k&&k+p[][k][i]->=j){
while(l<=r&&p[][que[r]][i]>=p[][k][i])
r--;
que[++r]=k--;
}
while(l<=r&&que[l]>j)
l++;
re[j][i]=min(min(j-que[r]+,p[][que[l]][i]),re[j][i]);
}
}
int ans=;
for(int i=;i<=*n;i++){
for(int j=((i^)&)+;j<=*m+;j+=)
if((i&)==(j&))
ans+=re[i][j]>>;
}
printf("%d",ans);
}
04-18 18:07