题意：在平面直角坐标系内给出一些与坐标轴平行的矩形，将这些矩形覆盖的区域求并集，然后问这个区域的周长是多少。（边与边重合的地方不计入周长）

分析：线段树。曾经做过类似的求矩形覆盖的总面积的题。这道题同样要使用扫描线算法。属于线保留型线段树。

我们先领扫描线与y轴平行。

线段树内每个节点除了要记录该区间被覆盖了几层之外，还要记录当前状态下扫描线在该区间（开区间）内与多少条与x轴平行的边相交。

节点上还有两个bool型变量，记录该区间内（包括子树）线段覆盖是否接触到该区间的起始和结束点。

在父节点如果没被整个覆盖，则需要从子区间的起始和结束点来更新父节点两端点的覆盖情况。

更新过程在返回时，父节点的交点数量应等于两子节点交点数量的和，另外特判一下两子区间的公共点（父节点的中点），判断这里是不是覆盖与未覆盖的分界点，如果是则还需要在父节点上增加这个交点。

这样就得知了每段与x轴平行的距离内有多少条线段需要计算，距离乘以数量即可。这样就计算出了所有与x轴平行的周长上的边的总长度。

之后让扫描线与x轴平行即可计算出与y轴平行的所有周长上的边的总长度。

#include 
      
       #include 
       
        using namespace std;//scanning from left to right//discretionize Ys#define MAX_REC_NUM 5005#define MAX_INTERVAL MAX_REC_NUM * 2struct Node{    int    l, r;    Node    *pleft, *pright;    int    num;    bool    to_left, to_right;        int    edge_num;};int    node_cnt;Node    tree[MAX_INTERVAL * 3];struct Interval{    int start, end;    int pos;    int value;    Interval()    {}    Interval(int start, int end, int pos, int value):start(start), end(end), pos(pos), value(value)    {}    bool operator < (const Interval &a)const    {        if (pos != a.pos)            return pos < a.pos;        return value > a.value;    }}interval[MAX_REC_NUM * 2];struct Rectangle{    int l, d, u, r;}rec[MAX_REC_NUM];int discrete[MAX_REC_NUM * 2];int discrete_num;int rec_num;int interval_num;int get_index(int a){    return lower_bound(discrete, discrete + discrete_num, a) - discrete;}void discretization(int discrete[], int &discrete_num){    sort(discrete, discrete + discrete_num);    discrete_num = unique(discrete, discrete + discrete_num) - discrete;}void input(){    scanf("%d", &rec_num);    for (int i = 0; i < rec_num; i++)    {        int l, d, r, u;        scanf("%d%d%d%d", &l, &d, &r, &u);        rec[i].l = l;        rec[i].r = r;        rec[i].u = u;        rec[i].d = d;    }}void make_xscan(){    discrete_num = 0;    interval_num = 0;    for (int i = 0; i < rec_num; i++)    {        int l, d, r, u;        l = rec[i].l;        r = rec[i].r;        u = rec[i].u;        d = rec[i].d;        interval[interval_num++] = Interval(d, u, l, 1);        interval[interval_num++] = Interval(d, u, r, -1);        discrete[discrete_num++] = u;        discrete[discrete_num++] = d;    }}void make_yscan(){    discrete_num = 0;    interval_num = 0;    for (int i = 0; i < rec_num; i++)    {        int l, d, r, u;        l = rec[i].l;        r = rec[i].r;        u = rec[i].u;        d = rec[i].d;        interval[interval_num++] = Interval(l, r, d, 1);        interval[interval_num++] = Interval(l, r, u, -1);        discrete[discrete_num++] = l;        discrete[discrete_num++] = r;    }}void buildtree(Node *proot, int s, int e){    proot->l = s;    proot->r = e;    proot->to_left = false;    proot->to_right = false;    proot->num = 0;    proot->edge_num = 0;    if (s == e)    {        proot->pleft = proot->pright = NULL;        return;    }    node_cnt++;    proot->pleft = tree + node_cnt;    node_cnt++;    proot->pright = tree + node_cnt;    buildtree(proot->pleft, s, (s + e) / 2);    buildtree(proot->pright, (s + e) / 2 + 1, e);}void recount(Node *p){    if (p->num > 0)    {        p->edge_num = 0;        p->to_right = p->to_left = true;        return;    }    if (p->pleft == NULL || p->pright == NULL)    {        p->edge_num = 0;        p->to_right = p->to_left = false;        return;    }    p->to_left = p->pleft->to_left;    p->to_right = p->pright->to_right;    p->edge_num = p->pleft->edge_num + p->pright->edge_num;    if (p->pleft->to_right != p->pright->to_left)        p->edge_num++;}void insert(Node *proot, int s, int e, int value){    if (s > proot->r || e < proot->l)        return;    s = max(s, proot->l);    e = min(e, proot->r);    if (s == proot->l && e == proot->r)    {        proot->num += value;        recount(proot);        return;    }    insert(proot->pleft, s, e, value);    insert(proot->pright, s, e, value);    recount(proot);}long long work(){    long long ans = 0;    for (int i = 0; i < interval_num; i++)    {        int s = get_index(interval[i].start);        int e = get_index(interval[i].end) - 1;        insert(tree, s, e, interval[i].value);        long long line_num = tree->edge_num;        if (tree->to_left)            line_num++;        if (tree->to_right)            line_num++;        if (i != interval_num - 1)            ans += (interval[i + 1].pos - interval[i].pos) * line_num;    }    return ans;}int main(){    input();    long long ans = 0;    make_xscan();    sort(interval, interval + interval_num);    discretization(discrete, discrete_num);    buildtree(tree, 0, discrete_num);    ans += work();    make_yscan();    sort(interval, interval + interval_num);    discretization(discrete, discrete_num);    buildtree(tree, 0, discrete_num);    ans += work();    printf("%lld\n", ans);    return 0;}