[HOJ 164] 森森砍你的臉

作法：

考慮枚舉正方形左上角右下角所在的對角線，首先我們可以預處理出每個格子的$X$值和$Y$值，$X[i][j]$代表從$(i,j)$這格往右往下長度$X[i][j]$以內的格子都是$1$（或是$(i,j),...,(i,j+X[i][j]-1)$均為$1$，往下同理），$Y[i][j]$則是代表往左往上的，並且兩者都是取最大的值。那麼當我們枚舉一條對角線時，記這條對角線上第$i$格的$X,Y$值分別為$x[i],y[i]$，那我們想找的就是所有二元組$(i,j)$的數量（$i\leq j$），滿足$x[i]\geq j-i+1$，且$y[j]\geq j-i+1$。注意到這條式子中，不管怎麼樣當$i>j$時他一定會成立，因此我們可以把$i\leq j$這個條件拿掉，再扣掉多算到的部份就可以了。將上式移項得$i+x[i]\geq j+1$，$i\geq j+1-y[j]$，那麼就可以轉換成簡單的問題了：考慮平面上的$n$個紅點和$n$個藍點，其中第$i$個紅點的座標為$(i+x[i],i)$，第$i$個藍點的座標為$(i+1,i+1-y[i])$，求滿足「紅點的兩座標均$\geq$藍點的兩座標」的（紅點、藍點）的個數（或是說紅點包住藍點的點對數量）。這可以先把所有點按照$x$座標排序，再用個 BIT 查詢每個紅點包住了幾個藍點就可以了。

code :

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=1000+10 ;
 
struct event
{
    int x,y,type ;
    bool operator < (const event &rhs) const
    {
        return x==rhs.x ? type<rhs.type : x<rhs.x ;
    }
};
 
int bit[maxn] ;
void add(int x)
{
    for(;x<maxn;x+=lowbit(x)) bit[x]++ ;
}
int query(int x)
{
    int ret=0 ;
    for(;x;x-=lowbit(x)) ret+=bit[x] ;
    return ret ;
}
 
char G[maxn][maxn] ;
int u[maxn][maxn],d[maxn][maxn],l[maxn][maxn],r[maxn][maxn] ;
vector<event> v[2*maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%s",G[i]+1) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        u[i][j]=(G[i][j]=='1' ? u[i-1][j]+1 : 0) ,
        l[i][j]=(G[i][j]=='1' ? l[i][j-1]+1 : 0) ;
    for(int i=n;i>=1;i--) for(int j=n;j>=1;j--)
        d[i][j]=(G[i][j]=='1' ? d[i+1][j]+1 : 0) ,
        r[i][j]=(G[i][j]=='1' ? r[i][j+1]+1 : 0) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        v[i-j+n].push_back((event){i,i+1-min(u[i][j],l[i][j]),1}) ,
        v[i-j+n].push_back((event){i+min(r[i][j],d[i][j]),i,2}) ;
    int ans=0 ;
    for(int i=1;i<2*n;i++)
    {
        sort(v[i].begin(),v[i].end()) ;
        memset(bit,0,sizeof(bit)) ;
        for(auto j : v[i])
        {
            if(j.type==1) add(j.y) ;
            else ans+=query(j.y) ;
        }
        int sz=v[i].size()/2 ;
        ans-=sz*(sz-1)/2 ;
    }
    printf("%d\n",ans) ;
}