USACO/window

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 5 .3中的OI题目Window Area的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

算法一

算法并不难，只要想清楚了就很容易写出程序了。 首先，对于每块放入的窗户，设定一个高度值。这个高度值应该是所有窗户中最大的。同时要维护两个值：所有窗户的最大高度和最小高度，初始时这两个值均为0。每次新放入窗户时，这个窗户的高度就设为最大高度+1，同时更新最大高度。置顶和置底的操作相应进行。去掉窗户时更新最大高度和最小高度。 这样前4个操作就很容易了。现在来考虑第5个操作。需要用到矩形切割的知识。 所谓矩形切割，就是把两个矩形不相交的部分切开，以利于统计。比如两个矩形a,b，如果a有在b左边的部分，那么就把它切下来；接下来如果有在b右边的部分，也切下来；同样，上下也可以仿照这种方法操作。 实现第5个操作需要开一个队列。初始时队首为待统计的矩形。实现的时候每次先找一个高度比待统计矩形高，且没有计算过的矩形，记录一下当前队尾。取出一个队首元素，用这个矩形切割队首，切得的所有矩形依次放入队尾。重复上述步骤直到当前队首等于原来的队尾。 所有符合的矩形都统计完以后，队列中所有矩形的面积和除以待统计矩形的面积就是这个操作的答案。

注：数据规模很小，最大的数据也只有600行而已，所以队列完全不必要用链队，数组即可。

算法二

其实思想和算法一是一样的，但是使用了字符串操作，大大简化了代码。另，计算面积时参考了3.1的rect1
详细实现可以参考源代码

算法三

（by dfs35123 http://dfs35123.spaces.live.com ） 这道题用的是矩形切割。（我所理解的）矩形切割就是某一个矩形被上面的矩形所切割，最多切成9个小矩形。 然后再用更上面一层的矩形（递归地）切割这切出来的周围8个小矩形，一直处理到上面每一层的矩形都结束。

我第一次做这个题用的方法是： 1.用一个数组win来记录每“层”对应的窗口。 2.每次新建窗口，新建一个最上层，放在最上层。 3.每次删除窗口，就把win[这一层]赋值为0对应的ASCII码。 4.每次置顶：在顶上新建一层，放在上面。删除原窗口。置底与置顶类似。 5.每次s()操作：对这个矩形调用矩形切割函数。用上面的每层来切割它。最后没有被覆盖的就是露着的面积。 这个方法很简单，所以我感觉这个题很简单。结果，一交，发现第10组数据超时。

这组数据的s操作相当多，其他操作很少。所以反复调用函数就会超时。

于是我想了一个新的方法。 用see[]记录某个矩形能看见的面积。每次新建、删除、置顶、置底都要维护，而s()就可以直接出结果。

1.新建窗口时：

 能看见面积=总面积。
 从上向下做矩形切割。
 下面的矩形减去被这个矩形盖住的面积。

2.置顶时：

 能看见面积=总面积。
 从上向下做矩形切割。
 这个矩形原来的位置以上的所有矩形减去相应的面积。原来位置一下的矩形面积不变。

3.置底时：

 能看见面积=总面积。
 从上向下做矩形切割。每次该矩形减去相应面积。
 原位置以上所有矩形面积不变。以下矩形加上相应面积。

4.删除时：

 从上向下做矩形切割。
 原位置以上所有矩形面积不变。以下矩形加上相应面积。

注意数据阴人。给出的矩形两个对角，可能是左上右下，也可能是左下右上！一定要处理！ 附：我写的矩形切割是自己发明的代码，不是正统的版本，比较麻烦。所以没有发到nocow上。想看的可以到http://dfs35123.spaces.live.com/blog/cns!A6CB032EC0980F16!565.entry

hydralisk:针对算法三小说明一下，矩形切割每次最多切出来4个就行了，而不是8个，这样写起来轻松一些，效率高一些。代码在java里面。（java真ws啊真ws）

算法四 漂浮法

//from Error

前面的四个操作在之前的算法中都已有描述，在此就不在阐述，主要说一下最后一个操作的面积计算法。

此题可以用到漂浮法。

在每次询问时，想象先将在被询问窗口之上的所有窗口按层次放入大海中，最后将被询问窗口放在最底端，由于浮力作用这个窗口会向上浮，在上浮时如果碰撞

到上方窗口时，则将这个窗口所有没被碰撞的部分继续执行上浮操作，直到浮出水面为止，就进行统计浮出水面的面积，所有浮出水面的面积之和就是可见的面

积。具体过程可以用递归来实现。

Pascal递归代码如下：

procedure try(k,x0,y0,x1,y1:longint);
 begin
  while (k>0)and((x1<=a[k].x0)or(x0>=a[k].x1)or(y1<=a[k].y0)or(y0>=a[k].y1)) do dec(k); //如果不发生碰撞则跳过
  if k=0 then begin area:=area+(x1-x0)*(y1-y0); exit; end; //如果浮出水面则累加面积
  if x0<a[k].x0 then begin try(k-1,x0,y0,a[k].x0,y1); x0:=a[k].x0; end; //分割左边未碰撞面后继续上浮
  if y0<a[k].y0 then begin try(k-1,x0,y0,x1,a[k].y0); y0:=a[k].y0; end; //分割下边未碰撞面后继续上浮
  if x1>a[k].x1 then begin try(k-1,a[k].x1,y0,x1,y1); x1:=a[k].x1; end; //分割右边未碰撞面后继续上浮
  if y1>a[k].y1 then begin try(k-1,x0,a[k].y1,x1,y1); y1:=a[k].y1; end; //分割上边未碰撞面后继续上浮
 end;

代码中a数组是按层次存放的所有窗口的左下角和右上角坐标，即a[1]代表最顶层窗口，a[n]代表最底层窗口。

详细请参见Pascal代码算法四。所有点全部0.000s。

算法五

每个window储存一个高度，前四个操作只需更改高度即可， s（X）时，统计出比X低的window， 坐标离散化，floodfill， 统计即可。

参考代码

C

C++

Pascal

Java