ZJOI 2012 Round 1 mrx 详细题解

有人说我那题的题解过于意识流。。。。

于是我就看了一下。。

发现没有看懂。。。。。

发现没有看懂。。。。。。

于是我来写一个详细的题解。。。

 

首先,我们倒过来计算空矩形的数量,答案就是 矩形的数量 – 空矩形的数量。

那么,我们按行扫描,每次计算底边在当前行上的空矩形的数量。

那么实际上这个的答案,只跟当前每列,往上能伸展多少有关。

不妨考虑是这样的图形。

让我们考虑如何计算答案。

由于底边已经确定了,那么我们需要选择的就是上边界和左右边界(也就是左上角和右上角)。

继续观察这个图形,划分一下,可以发现它能够看成一个树形结构。

注意到,左上角和右上角,必然都在划分过之后的同一个矩形块中!

设划分出来的矩形宽度为w,高度为h,那么在这个矩形中的答案就是C(w+1,2)*h。

在树的节点中维护它所有子孙的答案和。

由于这个是一个树形结构,我们可以用树来维护,同时因为数据是随机的,故树的高度是logn的,这个可以用随机笛卡尔树高来证明。

接下来我们是在一行行扫描,所以得考虑如何维护。

如果下一行是空的,我们只需要把最下面那个矩形,也就是树的根,的高度+1就行了,同时更新根的答案。

如果下一行中有障碍物。

比如在第c列。

画一下图可以发现,整棵树,被顺着第c列,切成了两部分。

我们只需要在切树的同时,维护树的结构和答案即可。维护的复杂度跟树高是相同的,所以总复杂度就是nlgn。

具体的代码我已发在我的网盘,我自认为写的还是挺可读的。

 

 

10 thoughts on “ZJOI 2012 Round 1 mrx 详细题解

  1. 找不到原题目的详细描述,但应该是不会错的:这个题目曾经是Google 2004年的面试题。它的一个简化版本,即矩形宽都=1的情况,有一个O(n)的算法

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>