传送门

题意：

给定一个 R∗C R ∗ C 的01 矩阵，要求计算出这个 01 矩阵中有多少个双十字。

双十字由两条水平的和一条竖直的“1”线段组成，要求满足以下几个限制：

1.两条水平的线段不能在相邻的两行。

2.竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。

3.竖直线段必须将两条水平线段严格划分成相等的两半。

4.上方的水平线段必须严格短于下方的水平线段。

输出双十字的个数 mod 1,000,000,009 的值。

R,C,N≤10000,R∗C≤1000000 R , C , N ≤ 10000 , R ∗ C ≤ 1000000

Solution：

lr[i] l r [ i ] 表示从i开始表示最多能左右延伸多少

down[i] d o w n [ i ] 表示从i开始最多往下延伸多少

top[i]表示从i开始最多往上延伸多少

我们考虑枚举下端线段的中点j，然后对于每个上端线段的中点i，对答案的贡献有

∑lr[j]len=1min(len−1,lr[i])∗top[i]∗down[j] ∑ l e n = 1 l r [ j ] m i n ( l e n − 1 , l r [ i ] ) ∗ t o p [ i ] ∗ d o w n [ j ]

min不是很好处理，我们想办法去掉它

尝试分类讨论：

当 lr[i]≤lr[j] l r [ i ] ≤ l r [ j ] 时，答案为 (lr[i]∗lr[j]−lr[i]∗(lr[i]+1)2)∗top[i]∗down[j] ( l r [ i ] ∗ l r [ j ] − l r [ i ] ∗ ( l r [ i ] + 1 ) 2 ) ∗ t o p [ i ] ∗ d o w n [ j ]

当 ＞lr[i]＞lr[j] ＞ l r [ i ] ＞ l r [ j ] 时，答案为 lr[j]∗(lr[j]−1)2∗top[i]∗down[j] l r [ j ] ∗ ( l r [ j ] − 1 ) 2 ∗ t o p [ i ] ∗ d o w n [ j ]

对于每一列的连续的非0区间，我们只需要把关于i的东西全部记录下来，每次结合j进行计算即可

用树状数组维护3个值：

1. −lr[i]∗(lr[i]+1)2∗top[i] − l r [ i ] ∗ ( l r [ i ] + 1 ) 2 ∗ t o p [ i ]

2. lr[i]∗top[i] l r [ i ] ∗ t o p [ i ]

3. top[i] t o p [ i ]

因为R和C 不确定，数组可能开不下，所以我们把矩阵压成一维

注意代码里是实时计算top
代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int l[10010],r[10010],lr[1200010],down[1200010],pos[1200010];
int tr[10010][3],n,m,p,ans,top=1;
const int mod=1e9+9;
int id(int x,int y){
  return (x-1)*m+y;}
int add(int id,int i,int x)
{
    //cout<<id<<" "<<i<<" "<<x<<endl;
    for (;i<=m;i+=(i&-i))
    {
        tr[i][id]+=x;
        if (tr[i][id]>=mod) tr[i][id]-=mod;
        if (tr[i][id]<0) tr[i][id]+=mod;
    }
}
int query(int id,int i)
{
    int ans=0;
    for (;i;i-=(i&-i))
    {
        ans+=tr[i][id];
        if (ans>=mod) ans-=mod;
        if (ans<0) ans+=mod;
    }
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for (int x,y,i=1;i<=p;i++) scanf("%d%d",&x,&y),pos[id(x,y)]=1;
    for (int i=1;i<=n;i++)
    {
        l[1]=(!pos[id(i,1)]);
        for (int j=2;j<=m;j++) if (!pos[id(i,j)]) l[j]=l[j-1]+1;else l[j]=0;
        r[m]=(!pos[id(i,m)]);
        for (int j=m-1;j>=1;j--) if (!pos[id(i,j)]) r[j]=r[j+1]+1;else r[j]=0;
        for (int j=1;j<=m;j++)
            lr[id(i,j)]=min(l[j],r[j])-1;
            //,cout<<i<<" "<<j<<" "<<lr[id(i,j)]<<endl;
    }
    for (int i=1;i<=m;i++)
    {
        down[id(n,i)]=(!pos[id(n,i)]);
        for (int j=n-1;j>=1;j--)
            if (!pos[id(j,i)]) down[id(j,i)]=down[id(j+1,i)]+1;
    }
    for (int i=1;i<=n*m;i++) if (down[i]) down[i]--;

    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (pos[id(j,i)]){memset(tr,0,sizeof(tr));top=j+1;continue;}
            ans=(1ll*query(0,lr[id(j,i)])*down[id(j,i)]+ans)%mod;
            ans=(1ll*query(1,lr[id(j,i)])*down[id(j,i)]%mod*lr[id(j,i)]+ans)%mod;
            ans=(1ll*(query(2,m)-query(2,lr[id(j,i)])+mod)*down[id(j,i)]%mod*lr[id(j,i)]*(lr[id(j,i)]-1)/2+ans)%mod;
        //  cout<<ans<<endl;
            if (j==1) continue;
            if (pos[id(j-1,i)]) continue;
            if (lr[id(j-1,i)])
            {
                add(0,lr[id(j-1,i)],(1ll*(-lr[id(j-1,i)]*(lr[id(j-1,i)]+1)/2)*(j-1-top)%mod+mod)%mod);
                add(1,lr[id(j-1,i)],lr[id(j-1,i)]*(j-1-top));
                add(2,lr[id(j-1,i)],j-1-top);
            }
        }
        memset(tr,0,sizeof(tr));top=1;
    }
    printf("%d",ans);
}