学步园

思路：第一回遇见 用到扫描线的题 找了资料和看解题报告才弄懂 （PS:解题报告都不附注释的。。。）
详细讲一下扫描线的使用吧 为自己也为以后要学的人一点帮助

1.将排序后的seg数组依次输入，执query函数 flag = 1 为插入边，flag = -1 为出边 修改 count的值
同时更新len和line

2.每扫描一次，就要计算一次周长pmt，这里我们以图中的例子来讲解过程：

   首先是AB，它被插入线段树，pmt = pmt +
|AB|；

 
 然后是EG，它被插入线段树，此时线段树的root节点的测度为|EG|的值，但由于之前之前加过|AB|，因而应该减去|AB|
即（now_l），其实就是减去|KL|，然后再加上line*2*|AK|
(水平的长度)，这里的line的值是未插入EG时线段树的根节点的line值。

//356K   
32MS

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
#define M 5050
using namespace std;

struct tree
{
    int
l,r;
    int
lb,rb;    
//左右端点是否被覆盖
    int
count,line,len;   
//count 被覆盖的次数  line 所包含区间的数量 len 是区间长度（测度）
}node[M*3];

struct data
{
    int
x,y1,y2;
    int
flag;    
//flag 1表示为入边，-1表示为出边
}seg[M*2];

int
y[M*2];    
//记录y坐标

bool cmp(data a,data b)  //x升序 x相同时 入边在前
{
    if (a.x
< b.x)
       
return true;
    if (a.x ==
b.x&&a.flag >
b.flag)
       
return true;
    return
false;
}
void BuildTree(int left,int right,int u)
{
    node[u].l =
left;
    node[u].r =
right;
    node[u].len
= node[u].line = node[u].count = 0;
    if (left + 1
== right)
       
return ;
    int mid =
(left+right)>>1;
   
BuildTree(left,mid,L(u));
   
BuildTree(mid,right,R(u));
}
void updata (int u)  //更新测度 和 line的值
{                  
//获得以当前接点为根的树被覆盖的区间总长度 被覆盖区间的总数
    if
(node[u].count > 0) 

    {
       
node[u].len = y[node[u].r] - y[node[u].l];
       
node[u].line = node[u].lb = node[u].rb = 1;
    }
    else if
(node[u].l + 1 == node[u].r)
    {
       
node[u].len = 0;
       
node[u].line = node[u].lb = node[u].rb = 0;
    }
   
else    
//由左右结点的值 确定父亲结点的值
    {
       
node[u].len = node[L(u)].len + node[R(u)].len;
       
node[u].lb = node[L(u)].lb;
       
node[u].rb = node[R(u)].rb;
       
node[u].line = node[L(u)].line + node[R(u)].line -
node[L(u)].rb*node[R(u)].lb;
    }
}
void query (int left,int right,int flag,int u)
{
    if
(y[node[u].l] == left&&y[node[u].r]
== right)
    {
       
node[u].count += flag;
       
updata (u);
       
return ;
    }
    int mid =
y[(node[u].l + node[u].r)>>1];
    if (right
<= mid)
       
query (left,right,flag,L(u));
    else if
(left >= mid)
       
query (left,right,flag,R(u));