[HNOI2012]双十字

Description

在C 部落，双十字是非常重要的一个部落标志。所谓双十字，如下面两个例子，由两条水平的和一条竖直的“1”线段组成，要求满足以下几个限制：

我们可以找到 5 个满足条件的双十字，分别如下：

注意最终的结果可能很大，只要求输出双十字的个数 mod 1,000,000,009 的值

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

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

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

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

所以上面右边的例子是满足要求的最小的双十字。

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

例如下面这个例子，R=6,C=8，01 矩阵如下：

Input

第一行为用空格隔开的两个正整数 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可能稍大于原设定)

Output

D mod 1,000,000,009 的结果，其中D 为要求的 01

矩阵中双十字的个数。

Sample Input

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

Sample Output

题解：

首先因为R与C不确定，所以我们需要将点们放在一个一维数组中，算算编号就好了

接下来记录lr[i]与down[i]分别表示点i最多可以向左右延伸和向下延伸多少个1(不包括自己)

然后我们枚举双十字的下面那个交点，推一推公式：

{注：len是下面横线的长度，top表示能到达的最上的位置（连续的1），j是上面的横线的中心位置}

对于一个点i，它对答案的贡献是：$$sum_{len=1}^{lr[i]} {min⁡(lr[j],len-1)*(j-top)*down[i]}$$

显然这个min非常恶心，我们考虑把它拆开成下面的样子：

1.当(lr[j] <= len-1) 贡献是$$sum_{len=1}^{lr[i]} {lr[j]×(j-top)×down[i]}$$

2.当(lr[j] > len-1) 贡献是$$sum_{len=1}^{lr[i]} {(len-1)×(j-top)×down[i]}$$

再进一步变形：
1.当(lr[j] <= lr[i]) 贡献$$((lr[i]×lr[j]-lr[j]×frac{lr[j]+1}{2}×down[i]×(j-top))$$

2.当(lr[j] > lr[i]) 贡献是$$(lr[i]×frac{lr[i]-1}{2}×down[i]×(j-top))$$

（对于1的解释:　lr[i]×lr[j]是总方案数，lr[j]×(lr[j]+1)/2是不合法方案数）

现在，需要解决的是所有带j的式子，我们定义3个树状数组t1, t2, t3，分别记录:

1.$$(-lr[j]*frac{lr[j]+1}{2})×(j-top)$$

2.$$lr[j]×(j-top)$$

3.$$j-top$$

把lr[i]作为位置插入，先枚举列再枚举行，每次注意清空。

并且因为两根横线不能挨在一起，所以枚举点(i, j)插入(i-1, j)的值

  1 //Never forget why you start
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<cmath>
  7 #include<algorithm>
  8 #define mod (1000000009)
  9 using namespace std;
 10 typedef long long lol;
 11 int n,m,l,c[1300005],down[1300005];
 12 //c[]表示一个点最多能向左右两边延伸多少的长度
 13 //down[]表示一个点最多能向下延伸多少长度 
 14 bool map[1300005];
 15 lol ans=0;
 16 int p(int x,int y) {
 17     return (x-1)*m+y;
 18 }//计算坐标在数组中对应的值 
 19 int lowbit(int x) {
 20     return x&(-x);
 21 }
 22 struct BIT {
 23     int ord[10005],tot;//这个数组是树状数组的骚操作，每次记录修改的位置，然后清零的时候就不需要memset了 
 24     lol c[10005];
 25     void clean() {
 26         int i,j;
 27         for(i=1; i<=tot; i++)
 28             for(j=ord[i]; j<=m; j+=lowbit(j))c[j]=0;//清零的时候只要修改所记录的位置就好 
 29         tot=0;
 30     }
 31     void add(int x,lol v) {
 32         ord[++tot]=x;//记录修改位置 
 33         int i;
 34         for(i=x; i<=m; i+=lowbit(i))(c[i]+=v)%=mod;
 35     }
 36     lol query(int x) {
 37         int i;
 38         lol ans=0;
 39         for(i=x; i; i-=lowbit(i))
 40             (ans+=c[i])%=mod;
 41         return ans;
 42     }
 43 } t1,t2,t3;
 44 /*
 45 c[j]>c[i] c[i]*(c[i]-1)/2*(j-top)*down[i];
 46 c[j]<=c[i] c[i]*c[j]*(j-top)*down[i]-c[j]*(c[j]+1)/2*(j-top)*down[i]
 47 
 48 t1:-c[j]*(c[j]+1)/2*(j-top)
 49 t2:c[j]*(j-top)
 50 t3:(j-top)
 51 */
 52 //本题公式推导到最后就是这个样子 
 53 void solve() {
 54     int i,j;
 55     for(j=1; j<=m; j++) {
 56         t1.clean();
 57         t2.clean();
 58         t3.clean();//每换一列就要将树状数组清零 
 59         int top=0;
 60         for(i=1; i<=n; i++) {
 61             int t=p(i,j);
 62             if(map[t]) {
 63                 top=i;
 64                 t1.clean();
 65                 t2.clean();
 66                 t3.clean();
 67                 continue;
 68             }
 69             (ans+=1ll*t1.query(c[t])*down[t]%mod)%=mod;
 70             (ans+=1ll*t2.query(c[t])*c[t]*down[t]%mod)%=mod;
 71             (ans+=1ll*(t3.query(m)-t3.query(c[t]))*c[t]*(c[t]-1)/2*down[t]%mod)%=mod;
 72             t=p(i-1,j);
 73             if(i==1)continue;
 74             if(c[t]) {
 75                 t1.add(c[t],-1ll*c[t]*(c[t]+1)/2*(i-1-top-1));
 76                 t2.add(c[t],1ll*c[t]*(i-1-top-1));
 77                 t3.add(c[t],1ll*(i-1-top-1));
 78             }
 79         }//更新答案 
 80     }
 81 }
 82 int main() {
 83     int i,j;
 84     scanf("%d%d",&n,&m);
 85     scanf("%d",&l);
 86     for(i=1; i<=l; i++) {
 87         int x,y;
 88         scanf("%d%d",&x,&y);
 89         map[p(x,y)]=1;
 90     }
 91     for(i=1; i<=n; i++) {
 92         int now=0;
 93         for(j=1; j<=m; j++) {
 94             int t=p(i,j);
 95             if(map[t])now=j;
 96             else c[t]=j-now-1;
 97         }
 98         now=m+1;
 99         for(j=m; j>=1; j--) {
100             int t=p(i,j);
101             if(map[t])now=j;
102             else c[t]=min(c[t],now-j-1);
103         }
104     }//预处理出c[] 
105     for(i=n; i>=1; i--) {
106         for(j=1; j<=m; j++) {
107             int t=p(i,j);
108             if(map[t])down[t]=-1;
109             else if(i==n)down[t]=0;
110             else down[t]=down[p(i+1,j)]+1;
111         }
112     }//预处理出down[] 
113     solve();
114     printf("%lld
",ans);
115     return 0;
116 }