题目描述
在C 部落，双十字是非常重要的一个部落标志。所谓双十字，如下面两个例子，由两条水平的和一条竖直的”1“线段组成，要求满足以下几个限制： ![] 我们可以找到 5 个满足条件的双十字，分别如下：
注意最终的结果可能很大，只要求输出双十字的个数 mod 1,000,000,009 的值·两条水平的线段不能在相邻的两行。·竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。 ·竖直线段必须将两条水平线段严格划分成相等的两半。·上方的水平线段必须严格短于下方的水平线段。 所以上面右边的例子是满足要求的最小的双十字。现在给定一个 R*C的01 矩阵，要求计算出这个 01 矩阵中有多少个双十字。例如下面这个例子，R=6,C=8，01 矩阵如下：
输入输出格式
输入格式：
第一行为用空格隔开的两个正整数 R和C，分别表示01矩阵的行数和列数。输入文件第二行是一个非负整数N,表示01矩阵中”0“的个数。接下来的N行，每行为用空格隔开的两个正整数x和y(1<=x<=R,1<=y<=C)，表示(x,y)是一个”0“。数据保证N个”0“的坐标两两不同。数据保证R,C,N<=10,000,R*C<=1,000,000.(事实上R*C可能稍大于原设定)
输出格式：
D mod 1,000,000,009 的结果，其中D 为要求的 01矩阵中双十字的个数。
输入输出样例
输入样例#1：
6 8
12
1 2
1 3
1 4
1 6
2 2
3 2
3 3
3 4
3 7
6 4
6 6
4 8
输出样例#1：
5
因为10000×10000存不下，所以用编号代替坐标
首先DP求出L,R,U,D数组表示左右上下有多少个连续的1
一个点左右可拓展的长度应当是min(L,R)
枚举十字架中心在第几列
当了某一行，考虑以它作于下面一个横线的方案数
$\sum_{len=1}^{L[i]} min(L[j], len-1)×D[i]×(j-top)$
把min拆掉：
1.当len-1<=L[j],则$\sum_{len=1}^{L[i]} L[j]×D[i]×(j-top)$
2.当len-1>L[j]，则$\sum_{len=1}^{L[i]} (len-1)×D[i]×(j-top)$
可以变成：
1.当L[j]<=L[i],贡献$(L[i]-(L[j]+1)/2)×D[i]×(j-top)×L[j]$
2.当L[j]>L[i]，贡献$L[i]×(L[i]-1)/2×D[i]×(j-top)$
维护3个树状数组，分别维护：
$(j-top)$
$(j-top)*L[j]$
$(j-top)*L[j]*L[j]$
每一次碰到0或算完一列的答案要给树状数组清0
因为十字架上面的横线不能是i-1，所以考虑先算完i，再加入i-1
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int mp[],U[],D[],L[],R[],n,r,c;
int Mod=1e9+,f1[],f2[],f3[],inv2,top,ans,ed;
int get_id(int x,int y)
{
return c*(x-)+y;
}
int qpow(int x,int y)
{
int res=;
while (y)
{
if (y&) res=1ll*res*x%Mod;
x=1ll*x*x%Mod;
y>>=;
}
return res;
}
void add1(int x,int d,int N)
{
if (x==) return;
while (x<=N)
{
f1[x]+=d;
if (f1[x]>=Mod) f1[x]-=Mod;
x+=x&(-x);
}
}
void add2(int x,int d,int N)
{
if (x==) return;
while (x<=N)
{
f2[x]+=d;
if (f2[x]>=Mod) f2[x]-=Mod;
x+=x&(-x);
}
}
void add3(int x,int d,int N)
{
if (x==) return;
while (x<=N)
{
f3[x]+=d;
if (f3[x]>=Mod) f3[x]-=Mod;
x+=x&(-x);
}
}
int query1(int x)
{
int s=;
while (x)
{
s+=f1[x];
if (s>=Mod) s-=Mod;
x-=(x&(-x));
}
return s;
}
int query2(int x)
{
int s=;
while (x)
{
s+=f2[x];
if (s>=Mod) s-=Mod;
x-=(x&(-x));
}
return s;
}
int query3(int x)
{
int s=;
while (x)
{
s+=f3[x];
if (s>=Mod) s-=Mod;
x-=(x&(-x));
}
return s;
}
int get_van(int x,int y,int N)
{
int t=L[get_id(x,y)];
int as=;
int s2=query2(t),s3=query3(t);
as=(1ll*t*s2%Mod-1ll*(s3+s2)%Mod*inv2%Mod+Mod);
if (as>=Mod) as-=Mod;
int s1=(query1(N)-query1(t)+Mod);
if (s1>=Mod) s1-=Mod;
as=(as+1ll*t*(t-)%Mod*inv2%Mod*s1%Mod);
if (as>=Mod) as-=Mod;
return 1ll*as*D[get_id(x,y)]%Mod;
}
void update(int x,int y,int N)
{
int t=L[get_id(x,y)];
add1(t,x-top,N);
add2(t,1ll*(x-top)*t%Mod,N);
add3(t,1ll*(x-top)*t%Mod*t%Mod,N);
}
int main()
{int i,j,x,y,l;
cin>>r>>c;
cin>>n;
inv2=qpow(,Mod-);
memset(mp,-,sizeof(mp));
for (i=;i<=n;i++)
{
scanf("%d%d",&x,&y);
mp[get_id(x,y)]=;
}
for (i=;i<=r;i++)
{
for (j=;j<=c;j++)
{
if (mp[get_id(i,j)]==-)
mp[get_id(i,j)]=;
}
}
for (i=;i<=r;i++)
{
L[get_id(i,)]=;
for (j=;j<=c;j++)
if (mp[get_id(i,j-)]==&&mp[get_id(i,j)]==) L[get_id(i,j)]=L[get_id(i,j-)]+;
else L[get_id(i,j)]=;
R[get_id(i,c)]=;
for (j=c-;j>=;j--)
if (mp[get_id(i,j+)]==&&mp[get_id(i,j)]==) R[get_id(i,j)]=R[get_id(i,j+)]+;
else R[get_id(i,j)]=;
for (j=;j<=c;j++)
L[get_id(i,j)]=min(L[get_id(i,j)],R[get_id(i,j)]);
}
for (j=;j<=c;j++)
{
U[get_id(,j)]=;
for (i=;i<=r;i++)
if (mp[get_id(i-,j)]==&&mp[get_id(i,j)]==) U[get_id(i,j)]=U[get_id(i-,j)]+;
else U[get_id(i,j)]=;
D[get_id(r,j)]=;
for (i=r-;i>=;i--)
if (mp[get_id(i+,j)]==&&mp[get_id(i,j)]==) D[get_id(i,j)]=D[get_id(i+,j)]+;
else D[get_id(i,j)]=;
}
for (j=;j<=c;j++)
{top=;
ed=min(c-j,j-);
for (l=;l<=ed;l++)
f1[l]=f2[l]=f3[l]=;
for (i=;i<=r;i++)
{
if (top==&&mp[get_id(i,j)]==) top=i;
if (mp[get_id(i,j)]==&&top)
{
for (l=;l<=ed;l++)
f1[l]=f2[l]=f3[l]=;
top=;
continue;
}
if (top==) continue;
if (i==top) continue;
if (i-top>=&&L[get_id(i,j)]>)
{
ans=ans+get_van(i,j,ed);
if (ans>=Mod) ans-=Mod;
}
if (i-!=top&&L[get_id(i-,j)]>)
update(i-,j,ed);
}
}
cout<<ans;
}