学步园

题意：

给定n个矩形，求重叠两次以上的面积。

题解：

这跟hdu1542很类似，那道题是求重叠的面积，这题是求重叠两次以上的面积，不过原理相同。在建线段树前，先将y坐标离散化，根据x坐标排序所有的竖直线段；之后建树，然后遍历，矩形的左线段则[yi,yj]区间加一，右边则减一，这个就是线段y坐标离散化后的区间。

树的结点需要有cov标记覆盖情况，len记录该区间内重叠两次以上的长度，once记录该区间内重叠一次的长度。

之后我们每次修改时，判断cov的覆盖情况，cov>=2则该区间的全被覆盖两次，cov=1则需要看该区间中重叠一次和重叠两次以上的情况，cov=0则看该区间重叠两次以上的情况。

类似的题目：hdu1542求重叠的面积；hdu1828求矩形围成图形的周长。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
using namespace std;

const int maxn=2e3+10;
struct node{
    int l,r,cov;
    double len,once;
}e[maxn*4];
struct segment{
    double x,up,down;
    int cov;
}f[maxn];
double y[maxn];
int cmp(segment a,segment b)
{
    return a.x<b.x;
}
void build(int a,int b,int c)
{
    e[c].l=a;e[c].r=b;
    e[c].len=e[c].once=e[c].cov=0;
    if(a==b)return ;
    int mid=(a+b)/2;
    build(a,mid,2*c);
    build(mid+1,b,2*c+1);
}
void push_up(int c)
{
    if(e[c].cov>=2)
    {
        e[c].once=0;
        e[c].len=y[e[c].r+1]-y[e[c].l];
    }
    else if(e[c].cov==1)
    {
        if(e[c].l==e[c].r)e[c].len=0;
        else e[c].len=e[2*c].len+e[2*c+1].len+e[2*c].once+e[2*c+1].once;
        e[c].once=y[e[c].r+1]-y[e[c].l]-e[c].len;
    }
    else
    {
        if(e[c].l==e[c].r)e[c].len=e[c].once=0;
        else
        {
            e[c].len=e[2*c].len+e[2*c+1].len;
            e[c].once=e[2*c].once+e[2*c+1].once;
        }
    }
}
void update(int a,int b,int c,int val)
{
    if(e[c].l==a&&e[c].r==b)
    {
        e[c].cov+=val;
        push_up(c);
        return ;
    }
    int mid=(e[c].l+e[c].r)/2;
    if(b<=mid)update(a,b,2*c,val);
    else if(a>mid)update(a,b,2*c+1,val);
    else
    {
        update(a,mid,2*c,val);
        update(mid+1,b,2*c+1,val);
    }
    push_up(c);
}
int main()
{
    int n,tt=0;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int i,j,k,t=0,l,r;
        double x1,y1,x2,y2;
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            y[++t]=y1;f[t].x=x1;f[t].up=y2;f[t].down=y1,f[t].cov=1;
            y[++t]=y2;f[t].x=x2;f[t].up=y2;f[t].down=y1,f[t].cov=-1;
        }
        sort(y+1,y+t+1);
        sort(f+1,f+t+1,cmp);
        build(1,t,1);
        double ans=0;
        for(i=1;i<=t;i++)
        {
            if(i!=0)ans+=(f[i].x-f[i-1].x)*e[1].len;
            l=lower_bound(y+1,y+t+1,f[i].down)-y;
            r=lower_bound(y+1,y+t+1,f[i].up)-y-1;//由于yi代表的是[i,i-1]段，所以右区间需要减一
            update(l,r,1,f[i].cov);
        }
        printf("%.2f\n",ans);
    }
    return 0;
}