POJ-1177 Picture（线段树+扫描线）

链接：POJ-1177 Picture

题意

给出平面直角坐标系上$n$（$0\le n\le 5000$）个矩形，求所有矩形合并后的所有线段长度之和。

分析

以计算 水平线段（平行于$x$轴）的长度之和 为例，竖直扫描线（平行于$y$轴）水平扫过 各矩形的 左、右边界；

可以发现，每扫过单位水平长度，水平线段长度之和应当增加 当前竖直方向的线段数目$?2$；

故要用线段树维护竖直方向的覆盖线段数目，较为特殊的一点是，虽然是区间修改，但是并不需要下传延迟标记（lazy tag）,因为

1. 遍历同一矩形的左、右边界时分别需要加入、删除该覆盖，故线段树的增加和删除操作是成对出现的；
2. 我们只需要知道整体的覆盖线段数目，即线段树根节点的值，无需进一步区间查询操作；

随后计算 竖直线段（平行于$y$轴）的长度之和 ，做相同处理即可；

此外，要先对数据做离散化处理，不再用坐标，而是用第几号线段至第几号线段来表示边界，更便于处理，详见代码。

代码

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int maxn=1e4+10;
int n,X[maxn],N,Y[maxn],M;
struct rectangle
{
    int a,b,c,d;
}r[maxn];
struct border
{
    int l,r;       //该边界由线段l~r组成bool tag;      //tag=1,左边界/下边界；tag=0,右边界/上边界
};
vector<border> x[maxn],y[maxn];
void