有人说我那题的题解过于意识流。。。。
于是我就看了一下。。
发现没有看懂。。。。。
发现没有看懂
。。。。。。
于是我来写一个详细的题解。。。
首先，我们倒过来计算空矩形的数量，答案就是 矩形的数量 – 空矩形的数量。
那么，我们按行扫描，每次计算底边在当前行上的空矩形的数量。
那么实际上这个的答案，只跟当前每列，往上能伸展多少有关。
不妨考虑是这样的图形。
让我们考虑如何计算答案。
由于底边已经确定了，那么我们需要选择的就是上边界和左右边界（也就是左上角和右上角）。
继续观察这个图形，划分一下，可以发现它能够看成一个树形结构。
注意到，左上角和右上角，必然都在划分过之后的同一个矩形块中！
设划分出来的矩形宽度为w，高度为h，那么在这个矩形中的答案就是C(w+1,2)*h。
在树的节点中维护它所有子孙的答案和。
由于这个是一个树形结构，我们可以用树来维护，同时因为数据是随机的，故树的高度是logn的，这个可以用随机笛卡尔树高来证明。
接下来我们是在一行行扫描，所以得考虑如何维护。
如果下一行是空的，我们只需要把最下面那个矩形，也就是树的根，的高度+1就行了，同时更新根的答案。
如果下一行中有障碍物。
比如在第c列。
画一下图可以发现，整棵树，被顺着第c列，切成了两部分。
我们只需要在切树的同时，维护树的结构和答案即可。维护的复杂度跟树高是相同的，所以总复杂度就是nlgn。
具体的代码我已发在我的网盘，我自认为写的还是挺可读的。
那个意识流题解……为什么我看懂了呢 = =
bd 因为LS是神犇
您是咋通过 数据是随机的 想到算法的呢
回复applepi：因为您的题解很意识流
回复acmcs：您可能对于这种题见得比较少。
这题我在fjsc看过类似的
回复中国脑筋：太神了
看了这个题解…..我想到了SGU 494……..丽洁姐应该把4系列AK了吧……
看题解没看太懂，然后看代码懂了的路过……
找不到原题目的详细描述，但应该是不会错的：这个题目曾经是Google 2004年的面试题。它的一个简化版本，即矩形宽都=1的情况，有一个O(n)的算法