USACO/rect1

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

分析

最简单的方法是灌水法了，虽然很可能行不通的，但大多数朋友还是会去试一试的，因为这是第一直觉，也是最容易实现的。

方法

漂浮法

以逆序来进行放置，即n to 1。逆序的好处在于放置一个矩形后，俯视看到的就是最终俯视该矩形应该看到的。因为挡着它的矩形在之前已经放置好了，所以可直接统计，为递归创造了条件。每放一个矩形，可以想象成将其扔入一密度很大的海水底部，海分成了n层,然后矩形开始向上浮。在上浮过程中若碰撞到其他的矩形则断裂成几个小矩形，继续上浮，直到浮出水面。于是想到用个递归来模拟上浮过程。

procedure cover(l,r,s,d,k,col:integer);
  begin
    while (k<=n) and ((r<=x1[k]) or (l>=x2[k]) or (d<=y1[k]) or (s>=y2[k])) do
      inc(k);
    if k>n then begin ans[col]:=ans[col]+(r-l)*(d-s); exit; end;
    if l<=x1[k] then begin cover(l,x1[k],s,d,k+1,col); l:=x1[k]; end;
    if r>=x2[k] then begin cover(x2[k],r,s,d,k+1,col); r:=x2[k]; end;
    if s<=y1[k] then begin cover(l,r,s,y1[k],k+1,col); s:=y1[k]; end;
    if d>=y2[k] then begin cover(l,r,y2[k],d,k+1,col); d:=y2[k]; end;
  end;

按行灌水法

离散化先。然后，按行灌水（开矩阵灌水不行，空间限制通不过）。关键在于程序要有所优化，完全用指针操作数组，不要用下标引用。参见blackco3的C++代码。

---

这题主需要读入，和之前的矩形比较，分类讨论将之前的矩形分割即可，详见源程序 c++ yzc60991

灌水法

 
    fillchar (map,sizeof(map),1);
    for l:=1 to n do →放置每一个矩形
      for i:=x1[l] to x2[l]-1 do 
        for j:=y1[l] to y2[l] do
          map[i,j]:=color[l];

最后对map整体扫描一遍便可得到各种颜色的面积。 很可惜的是空间运行是远远不够的，只能换个角度了…… 基于对各个格子的考虑。也可以容易的写出下面的代码：

 
    for i:=1 to a do 
      for j:=1 to b do
        for l:=n downto 0 do  →{第0个矩形为矩形（a,b）,color[0]=1}
          if (x1[l]<i) and (x2[l]>=i) and (y1[l]<j) and (y2[l]>=j)
            then begin
                   inc(col[color[l]]);
                   break;
                 end.

两个算法只是角度不一样，复杂度都是O（nab）。但后一个空间比前一个小的多，且速度快的多（多了个break）。这个算法可以过10个数据，一共11个数据（usaco老是出一些bt的数据）// 个人觉得，usaco的数据已经够弱了......---路人丁.//其实usaco的数据一点都不bt,这题要我出，至少也得有一半卡时间的吧。。。路过。。rp++;// O(nab)的复杂度，对付n=1000，a=b=10000的数据显然是行不通的。第十一个数据就是这样的一个数据。

离散化

上面的算法到底是慢在那里呢？基于上述算法，我们对每一个1*1的方格都处理了一次。很显然这是不必要的。更多的方格可以连在一起处理。 所以也就很自然的想到了离散化：两个数组分别记录放置矩形的横坐标和纵坐标。

很容易发现这些离散化后的小矩形中的各个方格的颜色是相同的。在每一个离散矩形里选出一1*1的方格作为代表，计算它的颜色。这样就可以在一次中处理一个离散矩形里的颜色属性。 离散化显然是比原来的算法更进一步，离散后复杂度降到O（4n^3）。对付n=1000的数据还是弱了点（还是只能过10数据）。

仔细想一想。离散化后还是做了很多的不必要的工作。

如图，用前面的算法，要确定5*5=25个矩形的颜色。而实际上只有3重颜色，4个区域（实线围成），按照区域算，也只要确定4个区域的颜色属性，而不是25个。算法之所以慢的原因也就找到了：做了大量的不必要的工作。现在我们要做的是合并这些相同属性的格子，做最精简的工作。 怎么有效的去合并这些相同属性的子问题，是现在面临的首要问题。在原来算法的基础上，很容易想到的是用‘种子填充法’。我们以深搜时搜到某个区域的第一个格子为代表，记录该区域的面积。 本题不仅在时间上很苛刻，在空间上的障碍也是制约算法实现的难点，所以想出的算法必须考虑算法的有效性。 在dfs前预处理用一boolean数组记录相邻格子之间的连通情况（虚线为连通，实线为不连通）。基于空间上的开销太大，还是要采用离散思想，并对每个矩形进行压缩。离散后的空间开销只有8^6的boolean数组，压缩矩形后处理边的连用情况也快的多了。

当然也不一定要像上面的算法那样‘把能合并的都合并了’，其实只要不去做太多无谓的工作，一样可以得到很不错的效果。基于此思想的‘矩形切割’和‘线段树’就是很不错的算法。

离散化+倒序染色

现在我们从另一个角度思考“如何减少不必要的工作”。采用离散化+暴力染色法，最坏的情况是O(n^3)的（即最后一个数据），TLE。我们TLE的原因除了把矩形分割的过细，还对同一个格子重复染色多次，如何能做到对一个格子只染色一次呢？倒序染色+封闭染过色的格子！具体可以对平面的每一行开一个链表，存储这一行中的格子，染色后将这个格子删去（当然，你得用一定的手段使得最后我们还能查到这个格子染的颜色，推荐数组模拟链表）。 P.S : 最后一个数据大概在1.2S左右,前面都是秒出.其实可以不用记录格子的颜色,在每次染色的过程中就可以顺便统计一下。不过这个方法会超时，实现的时候需要倒序，对于已经染过色的需要从队列里删除。

补充：链表真是缩时利器丫......原本最后一点在USACO上通过时间>2s，使用链表优化之后，0.3s通过
                                                                                   --某受上文启发的OIER

矩形切割

此思想把矩形（a,b）看成是最先加入的矩形，颜色为1。然后每次依次加入矩形，将与其重叠的矩形分割后加入队列之后（去掉重叠的部分）。最后扫描一次队列即可得出各个颜色的面积。 具体分割方法如下：

黄色区域是黄色矩形和白色矩形的重叠部分:

       wx1=max(x1,px1);
       wx2=min(x2,px2);
       wy1=max(y1,py1);
       wy2=min(y2,py2);

以上就是重叠部分的坐标。 而原来的白色矩形被除去黄色区域以外，被分割成了四个小矩形。 上图只是一般情况，更多的被分割出的矩形面积为0。

---

我是华丽的分割线-----------

Maigo牛的矩阵切割上浮法，非常的强悍 每次将当前的这一层与上1层或n层比较 先从x轴判断 是否相离 然后判断y轴 如果相离就进行下一层的比较 如果有重叠部分则进行切割 切割这一部分可以参考2004年薛矛的NOI国家队集训论文，里面有详细的图解 代码请参考C++中的budaish1的代码 具体会标明 注：该代码严重高仿Maigo牛的代码 在此声明一下

By Shadow

线段树

上面所提到的算法都是动态处理的，还可以写出基于线段树的静态处理的方法。 如果采用二维线段树（每次最多有4个下降分支），复杂度为O(4nlogn)。由于空间的限制，必须进行压缩，这一点还不够，还要使用动态线段树处理才能突破空间这个头痛的问题。实现起来太繁琐。

为了解决空间这个难题，我们不得不牺牲时间换空间，我们只对x轴进行离散化，对每一列用一维线段树处理。

插入一线段：

 
  procedure insert(u:integer);
    begin
      if treec[u]>0 then exit;
      if (treel[u]>=y1[k]) and (treer[u]<=y2[k]) and (treec[u]=0)
        then begin treec[u]:=col[k]; exit; end;
      treec[u]:=-1;
      if (y1[k]<treer[2*u]) then insert(2*u);
      if (y2[k]>treel[2*u+1]) then insert(2*u+1);
    end;

统计各种颜色覆盖面积：

  procedure total(u:integer);
    begin
      if treec[u]=0 then exit;
      if treec[u]<>-1
        then inc(ff[treec[u]],(treer[u]-treel[u])*(pt[w+1]-pt[w]))
        else begin total(2*u); total(2*u+1); end;
      treec[u]:=0;
    end;

四分树

直接离散化+四分树（见C++ Code），不过最后一个点死也过不了，MLE，T_T，直接打表过了222.240.154.116

降维分割

（这个方法名字是我乱取的，和上面的线段树思想差不多。）

一开始用上面的逆序灌水法做的，时间复杂度为O(ABN)，这个方法避免了重复染色，但是最后一个点还是TLE。

因为矩形的特殊性，其覆盖的点数可以在O(1)时间内算出来，因此灌水法慢就慢在它是逐点进行染色。考虑上面的矩形分割法，二维的重叠问题情况比较多且处理起来比较麻烦，因此利用上面提到的按行处理技术，这样就可以把二维覆盖的问题转化为一维线段覆盖的问题，这样处理起来就方便很多，总共才4, 5种情况。因为下面的色块可能会被上面的切割成两个部分，因此就需要对两个部分分别进行递归（最后一个点1.4s多）。这个方法依然逆序染色，得到染色区间后立马就能算出区间内的点数。另外维护一个变量统计该行已染色的点数，那么白色的就是剩下的点。

代码参考C++/wisatbf1

参考代码

C

C++

Pascal

Java

外部链接

• USACO Training