题目链接：传送门
思路：
（1）建立线段的信息，每个线段存储l到r的线段的x位置和y的起始点与终点。
建立线段树的节点信息，每个节点代表一个区间的信息，x表示区间的横坐标的位置，l，r表示纵坐标的范围，flag表示是否标记过，cover表示线段的覆盖次数。
（2）先将y的位置按照从小到大排序，再将边按照x的先后位置排序，然后建树，这样可以依次求出那部分被覆盖了。
（3）建树：如果不是叶子节点就标记为false，否则是true
（4）插入新区域：如果先不断递归找到合适区域，再求出这个区域的面积，和一般的线段树操作基本相同。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = ;
struct Node{
double x,l,r;
int flag,cover;
}node[maxn<<];
struct LINE{
double x,y_up,y_down;
int flag;
}line[maxn];
double y[maxn];
bool cmp(LINE a,LINE b)
{
return a.x<b.x;
}
void build(int rt,int l,int r)
{
node[rt].l=y[l];
node[rt].r=y[r];
node[rt].flag=false;
node[rt].cover=;
node[rt].x=-;
if(l+==r) //表示一个叶子节点
{
node[rt].flag=true;
return ;
}
int mid=(l+r)>>;
build(rt<<,l,mid); //区间是连续的。
build(rt<<|,mid,r);
}
double Insert(int rt,double x,double l,double r,int flag)
{
if(l>=node[rt].r||r<=node[rt].l) return ;
if(node[rt].flag) //找到一个叶节点
{
if(node[rt].cover>) //覆盖次数大于1
{
double pre=node[rt].x;
double ans=(x-pre)*(node[rt].r-node[rt].l);
node[rt].x=x;
node[rt].cover+=flag;
return ans;
}
else
{
node[rt].x=x;
node[rt].cover+=flag;
return ;
}
}
double ans=;
ans+=Insert(rt<<,x,l,r,flag);
ans+=Insert(rt<<|,x,l,r,flag);
return ans;
}
int main(void)
{
int T,i,cnt,j,n;
double x1,y1,x2,y2;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(cnt=-,i=;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
y[++cnt]=y1;
line[cnt].x=x1;
line[cnt].y_down=y1;
line[cnt].y_up=y2;
line[cnt].flag=;
y[++cnt]=y2;
line[cnt].x=x2;
line[cnt].y_down=y1;
line[cnt].y_up=y2;
line[cnt].flag=-;
}
sort(y,y+cnt+);
sort(line,line+cnt+,cmp);
build(,,cnt);
double ans=;
for(i=;i<=cnt;i++)
{
ans+=Insert(,line[i].x,line[i].y_down,line[i].y_up,line[i].flag);
}
printf("%.2lf\n",ans);
}
return ;
}