HNOI2012 双十字 DP+树状数组优化

题目链接：bzoj点我:-) 洛谷点我:-) 题目描述: 在C 部落，双十字是非常重要的一个部落标志。所谓双十字，由两条水平的和一条竖直的”1“线段组成，要求满足以下几个限制： ·两条水平的线段不能在相邻的两行。 ·竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。 ·竖直线段必须将两条水平线段严格划分成相等的两半。 ·上方的水平线段必须严格短于下方的水平线段。 现在给定一个 R*C的01 矩阵，要求计算出这个 01 矩阵中有多少个双十字。注意最终的结果可能很大，只要求输出双十字的个数 mod 1,000,000,009 的值

输入格式： 第一行为用空格隔开的两个正整数 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矩阵中双十字的个数。

思路： 首先因为R与C不确定，所以我们需要将点们放在一个一维数组中，算算编号就好了 接下来记录lr[i]$lr[i]$与down[i]$down[i]$分别表示点i$i$最多可以向左右延伸和向下延伸多少个1(不包括自己)

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

{注：len是下面横线的长度，top表示能到达的最上的位置（连续的1），j是上面的横线的中心位置} 对于一个点i$i$，它对答案的贡献是： ∑lr[i]len=1min(lr[j],len−1)×down[i]×(j−top)$/sum_{len=1}^{lr[i]} min(lr[j], len-1)×down[i]×(j-top)$ 显然这个min非常恶心，我们考虑把它拆开成下面的样子： 1.当(lr[j] <= len-1) 贡献是∑lr[i]len=1lr[j]×down[i]×(j−top)$/sum_{len=1}^{lr[i]} lr[j]×down[i]×(j-top)$ 2.当(lr[j] > len-1) 贡献是∑lr[i]len=1(len−1)×down[i]×(j−top)$/sum_{len=1}^{lr[i]} (len-1)×down[i]×(j-top)$

再进一步变形： 1.当(lr[j] <= lr[i]) 贡献是(lr[i]×lr[j]−lr[j]×(lr[j]+1)/2)×down[i]×(j−top)$(lr[i]×lr[j]-lr[j]×(lr[j]+1)/2)×down[i]×(j-top)$ 2.当(lr[j] > lr[i]) 贡献是lr[i]×(lr[i]−1)/2×down[i]×(j−top)$lr[i]×(lr[i]-1)/2×down[i]×(j-top)$ （对于1的解释:　lr[i]×lr[j]是总方案数，lr[j]×(lr[j]+1)/2是不合法方案数）

现在，需要解决的是所有带j$j$的式子，我们定义3个树状数组t1, t2, t3，分别记录: 1.−lr[j]∗(lr[j]+1)/2)×(j−top)$-lr[j]*(lr[j]+1)/2)×(j-top)$ 2.lr[j]×(j−top)$lr[j]×(j-top)$ 3.(j−top)$(j-top)$ 把lr[i]作为位置插入，先枚举列再枚举行，每次注意清空。 并且因为两根横线不能挨在一起，所以枚举点(i, j)插入(i-1, j)的值

感想： 啊我是湖南的为什么这么难qwq 这题我初一的时候抄了一遍题解，然后高一又抄了一遍题解。。 比较怀疑小时候到底看懂了没。。 其实也不是特别难吧，还是可以想一想推一推的 下方程序中的top与解释有一点点不一样，是解释的top-1

代码：