题面描述

在二维xy平面中有N，1 <= N <= 1,000个矩形。矩形的四边是水平或垂直线段。矩形由左下角和右上角的点定义。每个角点都是一对两个非负整数，范围从0到50,000，表示其x和y坐标。

求出所有矩形的面积（重叠部分只算一次）

示例：考虑以下三个矩形：

矩形1：<（0,0）（4,4）>，

矩形2：<（1,1）（5,2）>，

矩形3：<（1,1）（2,5）>。

所有由这些矩形构造的简单多边形的总面积为18。

输入

输入由多个测试用例组成。一行4 -1分隔每个测试用例。一个额外的4 -1的行标志着输入的结束。在每个测试用例中，矩形都是一行一个地排列的。在矩形的每一行中，给出4个非负整数。前两个是左下角的x和y坐标。接下来的两个是右上角的x和y坐标。

输出

对于每个测试用例，输出所有简单多边形的总面积。

示例输入

0 0 4 4

1 1 5 2

1 1 2 5

-1 -1 -1 -1

0 0 2 2

1 1 3 3

2 2 4 4

-1 -1 -1 -1

-1 -1 -1 -1

示例输出

18

10

 

线段树的妙用之一——扫描线。

我们先将坐标离散化（然而这题数据小，不需要）

然后将一个矩形分成两半，存下它的下边界和上边界，并且用w记录哪个是上边界哪个是下边界。

这里先将上边界w=-1，下边界w=1（下面说为什么）

然后我们按照每个边界的y从小到大排序（如果y相同，先添加上界）。

这样预处理就完成了。

完后开始想线段树的含义。

节点表示其区间内被覆盖的点（不算重复）的数目。

那么我们假设一条边的长度为k，那么其覆盖的点的数量就是看k+1，于是为了方便起见，我们把边界都少存一位，这样我们就可以用这个表示边界长度了。

然后我们一条一条添加边，等效于在线段树区间内+w。

现在你知道为什么上边界w=-1了：标志着这个矩形结束了，就是把原来被覆盖的点撤回。

那么显然从上一个边界到下一个边界中矩形覆盖的面积就是tree[1]*上下边界距离。

把他们都加在一起就是答案，这样做是不是很巧妙的避免了重复面积啊（原因是被覆盖的点没有被重复计算）！

但是这样问题就变成了如何求被覆盖的点（不算重复）的数目了。

我们用lazy标记表示当前区间被一整条下边界完全经过，这样的边的边数。

如果lazy>0说明该区间被完全覆盖了。

如果lazy=0：

如果此时l=r，直接更新为0（显然）。

如果不是，我们就需要重新更新节点的值了，那就是他的左右儿子的节点个数和。

（思考lazy=0只是说明了该区间没有被完全覆盖，但是它可能被非完全经过的下边界覆盖了）

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;inline int read(){    int X=0,w=1; char ch=0;    while(ch<'0' || ch>'9') {
   if(ch=='-') w=-1;ch=getchar();}    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();    return X*w;}struct node{    int y;    int x1;    int x2;    int w;}edge[2001];bool cmp(node a,node b){    return a.y
         
          >1;    build(a*2,l,mid);    build(a*2+1,mid+1,r);    tree[a]=tree[a*2]+tree[a*2+1];    return;}void add(int a,int l,int r,int l1,int r1,int w){    if(r1
          
           r)return; if(l1<=l&&r<=r1){ lazy[a]+=w; if(lazy[a]>0)tree[a]=r-l+1;//完全覆盖，值为区间长 else if(l==r)tree[a]=0;//该点没有被覆盖，清零 else tree[a]=tree[a*2]+tree[a*2+1];//没有被完全覆盖，需要重新更新 return; } int mid=(l+r)>>1; add(a*2,l,mid,l1,r1,w); add(a*2+1,mid+1,r,l1,r1,w); if(lazy[a]==0)tree[a]=tree[a*2]+tree[a*2+1];//没有被完全覆盖，需要重新更新 return;}int main(){ bool ok=0; while(233){ int n=0; while(233){ int a=read(); int b=read(); int c=read(); int d=read(); if(a==b&b==c&&c==d&&a==-1){ if(!n)ok=1; break; } n++; edge[n*2-1].x1=a; edge[n*2-1].y=b; edge[n*2-1].x2=c; edge[n*2].y=d; edge[n*2-1].w=1;//到下界时加上该矩形 edge[n*2].w=-1;//到上界时去掉该矩形 edge[n*2].x1=edge[n*2-1].x1; edge[n*2].x2=edge[n*2-1].x2; } if(ok==1)break; sort(edge+1,edge+2*n+1,cmp); //根据上下界大小排序，从下往上扫描矩形 build(1,0,50000); ll h,ans=0; add(1,0,50000,edge[1].x1+1,edge[1].x2,edge[1].w); //建一个底 //因为是点数和，所有求长度的话要减去一个点就为长度 for(int i=2;i<=2*n;i++){ h=edge[i].y-edge[i-1].y;//下一个矩形的下界（或者刚才的矩形的上界）之差即为高 ans+=h*tree[1];//底乘高为面积 add(1,0,50000,edge[i].x1+1,edge[i].x2,edge[i].w);//加上新矩形（或减去旧矩形） } printf("%lld\n",ans); } return 0;}