YZOJ P2358 [ZJOI 2012]Naive – Matrix

YZOJ P2358 [ZJOI 2012]Naive – Matrix

时间限制:1000MS      内存限制:131072KB

难度:\(7.0\)

  • 题目描述

给出一个 \(R \times C\) 的矩阵,上面有 \(N\) 个 \(0\),其他的都是 \(1\),现在给出这些 \(0\) 的位置,要求求出有多少个子矩阵包含至少一个 \(0\) 。

  • 输入格式

第一行输入三个整数 \(R\)、\(C\)、\(N\) 。

接下来 \(N\) 行,每行两个整数 \(x\)、\(y\),表示 \(0\) 的坐标。

  • 输出格式

输出一个数表示子矩阵的个数。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据,\(R, C \leq 40000\),\(N \leq \min\{R \times C,100000\}\),所有 \(0\) 的位置两两不同且随机生成。

 

 

 

Source: BZOJ 2658


 

 

 

好题!

很显然的是转换「至少包含一个 \(0\) 子矩形的数量」为「不包含 \(0\) 的子矩形的数量」,然后就不会做了(。

想到扫描线,从上往下扫描,处理出每一个点向左向右向上能到达的最远距离,发现这一步骤可以使用单调栈!笛卡尔树维护,答案就是 \(\sum\limits_{x}{\frac{size_x \times \left(size_x+1\right)}{2}\times \left(height_x-height_{fa}\right)}\)

注:这里每个节点维护的是其对父亲节点的贡献

考虑如何由这一层的笛卡尔树转换至下一层。

发现笛卡尔树其实和 \(Treap\) 是一样的东西,再加上本题的权值 \(height\) 是随机的,所以就可以用 \(Treap\) 维护这一操作。跳层其实就是把所有节点的 \(pri\) 都加上 \(1\) ,然后把当前层所有值为 \(0\) 的节点的 \(pri\) 设为 \(0\) 即可。

时间复杂度 \(O(NlogN+NlogC)\) 。

 

 

 

 

发表评论

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