[POJ][3832][线段树] Posters

题目大意

平面上有一些“回型”图案，每一个“回型”是由一个大矩形中间挖去一个小矩形构成，大小矩形的四边都平行于坐标轴。

现在有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].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
后记


此题前前后后做了3天。主要原因是对线段树成段更新的不熟练（对延时标记处理得不够老练）。做此题之前只会成段赋值，不会成段增减。因此特地找到POJ 3468写了个成段增减的模板，为做此题打基础。（虽然后来发现此题与成段增减的关系貌似不大）
另外在调试此题的过程中，还发现了原先成段赋值模板（根据HDU 1698写的模板）的一处设计缺陷。在此模板中，将树中节点的int型延迟标记初始化为0，并根据延迟标记是否不为0来判断节点是否被更改。但这就产生了新的问题，若我想要将一个区间赋值为0该怎么办？此时延迟标记被赋值为0，节点会被误判为未更改。
历经千辛万苦，最终发现此题并不是什么成段增减。最终思路还是通过看作者题解得来的。

发表回复取消回复