[GZ/GXOI2019]与或和(单调栈)

题目链接

题解

看到这个首发平台就觉得是rainbowcat出的题,一看题面——都有Freda了,就确定是rainbowcat出的了。

这一题第一次写我写挂了orz

由于与运算和或运算在每一位上都是独立的,我们可以考虑对每一位进行计算。

我们先考虑与运算(其实两个运算是一样的)
于是就成了一个求一个矩阵中,有多少个0/1子矩阵,我们可以考虑用单调栈做。

有一个显然的结论

在一个 $N\times M$ 的矩阵中,以(n,m)为右下角的子矩阵共有 $N\times M$ 个

具体来讲,我们要求出一个s二维数组,s[i][j]表示(i,j)点上方有多少个连续的1,$O(N^2)$预处理

枚举每一个点,我们来计算以它为右下角的子矩阵个数,观察如下矩阵:

假设我们现在统计到(3,3),可以发现它的贡献=(3,2)处贡献+s[3][3] (与前面的组合+该列的组合)

但是,如果是这样一个矩阵:

(3,3)处的贡献=(3,2)处的贡献+s[3][3]-1 (1为非法矩阵的数目)

对于一般情况,在2处,A区域就没有意义,4处,B区域就没有意义

所以我们要维护一个单调栈,栈中元素k要满足s[i][k]单调递增(栈顶s[i][k]最大)

每次有元素出栈时,说明有部分答案不能产生贡献,见代码注释

对于或运算,求所有0子矩阵,全集-0子矩阵数目即是贡献。

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注