[HNOI2012]双十字

题目描述

在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：复制

输出样例#1：复制

因为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

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 using namespace std;
  6 int mp[1500001],U[1500001],D[1500001],L[1500001],R[1500001],n,r,c;
  7 int Mod=1e9+9,f1[50001],f2[50001],f3[50001],inv2,top,ans,ed;
  8 int get_id(int x,int y)
  9 {
 10   return c*(x-1)+y;
 11 }
 12 int qpow(int x,int y)
 13 {
 14   int res=1;
 15   while (y)
 16     {
 17       if (y&1) res=1ll*res*x%Mod;
 18       x=1ll*x*x%Mod;
 19       y>>=1;
 20     }
 21   return res;
 22 }
 23 void add1(int x,int d,int N)
 24 {
 25   if (x==0) return;
 26   while (x<=N)
 27     {
 28       f1[x]+=d;
 29       if (f1[x]>=Mod) f1[x]-=Mod;
 30       x+=x&(-x);
 31     }
 32 }
 33 void add2(int x,int d,int N)
 34 {
 35   if (x==0) return;
 36   while (x<=N)
 37     {
 38       f2[x]+=d;
 39       if (f2[x]>=Mod) f2[x]-=Mod;
 40       x+=x&(-x);
 41     }
 42 }
 43 void add3(int x,int d,int N)
 44 {
 45   if (x==0) return; 
 46   while (x<=N)
 47     {
 48       f3[x]+=d;
 49       if (f3[x]>=Mod) f3[x]-=Mod;
 50       x+=x&(-x);
 51     }
 52 }
 53 int query1(int x)
 54 {
 55   int s=0;
 56   while (x)
 57     {
 58       s+=f1[x];
 59       if (s>=Mod) s-=Mod;
 60       x-=(x&(-x));
 61     }
 62   return s;
 63 }
 64 int query2(int x)
 65 {
 66   int s=0;
 67   while (x)
 68     {
 69       s+=f2[x];
 70       if (s>=Mod) s-=Mod;
 71       x-=(x&(-x));
 72     }
 73   return s;
 74 }
 75 int query3(int x)
 76 {
 77   int s=0;
 78   while (x)
 79     {
 80       s+=f3[x];
 81       if (s>=Mod) s-=Mod;
 82       x-=(x&(-x));
 83     }
 84   return s;
 85 }
 86 int get_van(int x,int y,int N)
 87 {
 88   int t=L[get_id(x,y)];
 89   int as=0;
 90   int s2=query2(t),s3=query3(t);
 91     as=(1ll*t*s2%Mod-1ll*(s3+s2)%Mod*inv2%Mod+Mod);
 92   if (as>=Mod) as-=Mod;
 93   int s1=(query1(N)-query1(t)+Mod);
 94   if (s1>=Mod) s1-=Mod;
 95   as=(as+1ll*t*(t-1)%Mod*inv2%Mod*s1%Mod);
 96   if (as>=Mod) as-=Mod;
 97   return 1ll*as*D[get_id(x,y)]%Mod;
 98 }
 99 void update(int x,int y,int N)
100 {
101   int t=L[get_id(x,y)];
102   add1(t,x-top,N);
103   add2(t,1ll*(x-top)*t%Mod,N);
104   add3(t,1ll*(x-top)*t%Mod*t%Mod,N);
105 }
106 int main()
107 {int i,j,x,y,l;
108   cin>>r>>c;
109   cin>>n;
110   inv2=qpow(2,Mod-2);
111   memset(mp,-1,sizeof(mp));
112   for (i=1;i<=n;i++)
113     {
114       scanf("%d%d",&x,&y);
115       mp[get_id(x,y)]=0;
116     }
117   for (i=1;i<=r;i++)
118     {
119       for (j=1;j<=c;j++)
120     　　{
121       　　if (mp[get_id(i,j)]==-1)
122         　　mp[get_id(i,j)]=1;
123     　　}
124     }
125   for (i=1;i<=r;i++)
126     {
127       L[get_id(i,1)]=0;
128       for (j=2;j<=c;j++)
129       if (mp[get_id(i,j-1)]==1&&mp[get_id(i,j)]==1) L[get_id(i,j)]=L[get_id(i,j-1)]+1;
130       else L[get_id(i,j)]=0;
131       R[get_id(i,c)]=0;
132       for (j=c-1;j>=1;j--)
133       if (mp[get_id(i,j+1)]==1&&mp[get_id(i,j)]==1) R[get_id(i,j)]=R[get_id(i,j+1)]+1;
134       else R[get_id(i,j)]=0;
135       for (j=1;j<=c;j++)
136     　　L[get_id(i,j)]=min(L[get_id(i,j)],R[get_id(i,j)]);
137     }
138   for (j=1;j<=c;j++)
139     {
140       U[get_id(1,j)]=0;
141       for (i=2;i<=r;i++)
142     　　if (mp[get_id(i-1,j)]==1&&mp[get_id(i,j)]==1) U[get_id(i,j)]=U[get_id(i-1,j)]+1;
143     　　else U[get_id(i,j)]=0;
144       D[get_id(r,j)]=0;
145       for (i=r-1;i>=1;i--)
146       if (mp[get_id(i+1,j)]==1&&mp[get_id(i,j)]==1) D[get_id(i,j)]=D[get_id(i+1,j)]+1;
147       else D[get_id(i,j)]=0;
148     }
149   for (j=1;j<=c;j++)
150     {top=0;
151       ed=min(c-j,j-1);
152       for (l=0;l<=ed;l++)
153     f1[l]=f2[l]=f3[l]=0;
154       for (i=1;i<=r;i++)
155     　　{
156       　　if (top==0&&mp[get_id(i,j)]==1) top=i;
157       　　if (mp[get_id(i,j)]==0&&top)
158         　　{
159           　　for (l=0;l<=ed;l++)
160         　　f1[l]=f2[l]=f3[l]=0;
161           　　top=0;
162           　　continue;
163         　　}
164       　　if (top==0) continue;
165       　　if (i==top) continue;
166       　　if (i-top>=3&&L[get_id(i,j)]>1)
167         　　{
168           　　ans=ans+get_van(i,j,ed);
169           　　if (ans>=Mod) ans-=Mod;
170         　　}
171       　　if (i-1!=top&&L[get_id(i-1,j)]>0)
172         　　update(i-1,j,ed);
173     　　}
174     }
175   cout<<ans;
176 }