题目大意
平面上有一些“回型”图案，每一个“回型”是由一个大矩形中间挖去一个小矩形构成，大小矩形的四边都平行于坐标轴。
现在有n个不同大小的“回型”图案，他们可能互相重叠，请求出被他们所覆盖的平面的总面积。
思路
首先，将每个一个回型划分为四个矩形。将每个矩形的与x轴平行的边按离x轴距离由近及远顺序插入线段树中（底边插入，顶边删除）。
在对每条线段执行插入之前，先计算下当前线段与上一条线段之间的覆盖面积。用tree[1].len*当前线段与前一个线段之间的距离（高度差），tree[1].len表示图形的宽。
当遍历完所有线段时，就会得出覆盖面积。
代码
#include
#include
using namespace std;
#define MAXSIZE 50000
#define N 50000
struct node
{
int total;
//total表示该节点所表示的区间被线段覆盖的次数
int left;
int right;
int len;
//该区间内，线段的长度。
}tree[MAXSIZE*3];
struct line
{
int pos;
//pos表示y轴坐标
int left;
int right;
bool top;
//判断该线段是否是矩形的上边界。
}edge[N*8];
int total_edge,n;
//一共total_edge个线段，n个回型。
void create(int root,int left,int right)
//建树，明确每个节点对应的区间
{
tree[root].left=left;
tree[root].right=right;
if(left==right)
return ;
int middle=(left+right)/2;
create(2*root,left,middle);
create(2*root+1,middle+1,right);
}
void updata(int root,int left,int right,int val)
//将线段插入或删除。
{
if(tree[root].left>right||tree[root].right<left)
return ;
else if(left<=tree[root].left&&tree[root].right0)
tree[root].len=tree[root].right-tree[root].left+1;
else if(tree[root].right==tree[root].left)
tree[root].len=0;
else
tree[root].len=tree[2*root].len+tree[2*root+1].len;
}
void add_edge(int pos,int left,int right,bool top)
//记录一条线段的信息
{
if(left>right)
return;
edge[total_edge].pos=pos;
edge[total_edge].left=left;
edge[total_edge].right=right;
edge[total_edge].top=top;
total_edge++;
}
int cmp(const void* m,const void* n)
//将线段按照y轴坐标由小到大排序。
{
return (*(line*)m).pos-(*(line*)n).pos;
}
void init()
//初始化及输入
{
total_edge=0;
for(int i=1;i<MAXSIZE*3;i++)
{
tree[i].len=0;
tree[i].total=0;
}
for(int i=0;i<n;i++)
{
int x1,y1,x2,y2,x3,y3,x4,y4;
scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
add_edge(y1+1,x1+1,x3,false);
add_edge(y2+1,x1+1,x3,true);
add_edge(y1+1,x3+1,x4,false);
add_edge(y3+1,x3+1,x4,true);
add_edge(y4+1,x3+1,x4,false);
add_edge(y2+1,x3+1,x4,true);
add_edge(y1+1,x4+1,x2,false);
add_edge(y2+1,x4+1,x2,true);
}
}
int main()
{
create(1,1,MAXSIZE+1);
while(scanf("%d",&n)&&n)
{
init();
qsort(edge,total_edge,sizeof(edge[0]),cmp);
long long total_size=0;
for(int i=0,pre=1;i<total_edge;i++)
{
total_size+=(long long)tree[1].len*(edge[i].pos-pre);
//这里注意，tree[1].len必须转化为long long型
updata(1,edge[i].left,edge[i].right,edge[i].top?-1:1);
pre=edge[i].pos;
}
printf("%I64d\n",total_size);
}
}
后记
此题前前后后做了3天。主要原因是对线段树成段更新的不熟练（对延时标记处理得不够老练）。做此题之前只会成段赋值，不会成段增减。因此特地找到POJ 3468写了个成段增减的模板，为做此题打基础。（虽然后来发现此题与成段增减的关系貌似不大）
另外在调试此题的过程中，还发现了原先成段赋值模板（根据HDU 1698写的模板）的一处设计缺陷。在此模板中，将树中节点的int型延迟标记初始化为0，并根据延迟标记是否不为0来判断节点是否被更改。但这就产生了新的问题，若我想要将一个区间赋值为0该怎么办？此时延迟标记被赋值为0，节点会被误判为未更改。
历经千辛万苦，最终发现此题并不是什么成段增减。最终思路还是通过看作者题解得来的。