题解--[ZJOI2009]对称的正方形

· · 题解

讲一下 manacher 的做法，这是一个很好的 manacher 练习题。
题目要求上下左右都对称的正方形个数，所以我们得通过上下对称和左右对称两个方面来限制。
我们先用 manacher 算法，得出对于每个格子在行方向上能延伸多远，记为 h_{i,j}，然后再得出每个格子在列方向上能延伸多远，记为 l_{i,j}。
然后我们发现，如果一个正方形要满足上下对称，那么对于最中间的那一行，在列方向上能延伸的回文串长度肯定要大于等于正方形的边长。左右对称同理。于是我们就可以用二分来得到单看满足上下对称/左右对称，这个正方形的边长最大是多少。
具体来说（以左右对称为例），假设我们现在枚举的整个正方形的中心为 i,j。我们二分一个 mid，检验方式是对于任意 k\in[i-mid+1,i+mid-1] 行的第 j 列的 h_{k,j} 必须都大于等于 mid。
得到两个方向的边长（实际上是中心到边缘的距离）后，因为我们在其中插入了 0，所以不能直接得到答案，设两个方向上中心到边缘的距离的最小值为 v。对于每一个以真实的数字为中心的点，答案是 \lceil\dfrac{v}{2}\rceil，对于每个以插入的 0 为中心的点，答案是 \lfloor\dfrac{v}{2}\rfloor。 

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int a[maxn][maxn],n,m,lg2[maxn],f[13][maxn],h[maxn][maxn],l[maxn][maxn],p[maxn],hl[maxn][maxn],ll[maxn][maxn],ans;
void solveh(int k) {
    int s[maxn],mr=0,mid=0;
    memset(p,0,sizeof(p));
    for(int i=0; i<=2*m; i++)s[i]=a[k][i];
    for(int i=0; i<=2*m; i++) {
        if(i<mr)p[i]=min(p[2*mid-i],mr-i);
        while(i-p[i]>=1&&i+p[i]<=2*m-1&&s[i-p[i]-1]==s[i+p[i]+1])p[i]++;
        if(i+p[i]>mr)mid=i,mr=i+p[i];
        h[k][i]=p[i];
    }
}
void solvel(int k) {
    int s[maxn],mr=0,mid=0;
    memset(p,0,sizeof(p));
    for(int i=0; i<=2*n; i++)s[i]=a[i][k];
    for(int i=0; i<=2*n; i++) {
        if(i<mr)p[i]=min(p[2*mid-i],mr-i);
        while(i-p[i]>=1&&i+p[i]<=2*n-1&&s[i-p[i]-1]==s[i+p[i]+1])p[i]++;
        if(i+p[i]>mr)mid=i,mr=i+p[i];
        l[i][k]=p[i];
    }
}//manacher
void buildst(int n) {
    for(int j=1; j<=lg2[n]; j++)
        for(int i=1; i<=n-(1<<j)+1; i++)f[j][i]=min(f[j-1][i],f[j-1][i+(1<<j-1)]);
}
int ask(int l,int r) {
    int len=lg2[r-l+1];
    return min(f[len][l],f[len][r-(1<<len)+1]);
}//st表处理区间min
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=2*max(n,m); i++)lg2[i]=lg2[i-1]+((1<<lg2[i-1]+1)==i);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)scanf("%d",&a[i*2-1][j*2-1]);
    for(int i=1; i<=2*n-1; i++)solveh(i);
    for(int j=1; j<=2*m-1; j++) {
        for(int i=1; i<=2*n-1; i++)f[0][i]=h[i][j];
        buildst(2*n-1);
        for(int i=1; i<=2*n-1; i++) {
            int l=1,r=min(i,2*n-i),ans=0;
            while(l<=r) {
                int mid=l+r>>1;
                if(ask(i-mid+1,i+mid-1)>=mid)ans=mid,l=mid+1;
                else r=mid-1;
            }
            hl[i][j]=ans;//左右对称
        }
    }
    for(int i=1; i<=2*m-1; i++)solvel(i);
    for(int i=1; i<=2*n-1; i++) {
        for(int j=1; j<=2*m-1; j++)f[0][j]=l[i][j];
        buildst(2*m-1);
        for(int j=1; j<=2*m-1; j++) {
            int l=1,r=min(j,2*m-j),ans=0;
            while(l<=r) {
                int mid=l+r>>1;
                if(ask(j-mid+1,j+mid-1)>=mid)ans=mid,l=mid+1;
                else r=mid-1;
            }
            ll[i][j]=ans;//上下对称
        }
    }
    for(int i=1; i<=2*n-1; i++)
        for(int j=1; j<=2*m-1; j++) {
            int v=min(hl[i][j],ll[i][j]);
            if((i&1)&&(j&1))ans+=(v+1)/2;
            else if(!(i&1)&&!(j&1))ans+=v/2;//统计答案
        }
    printf("%d",ans);
    return 0;
}