poj1177

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

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

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

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

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

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

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

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

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

#include <cstdio>

#include <algorithm>

using namespace std;

//scanning from left to right

//discretionize Ys

#define MAX_REC_NUM 5005

#define MAX_INTERVAL MAX_REC_NUM * 2

struct Node

{

    int    l, r;

    Node    *pleft, *pright;

    int    num;

    bool    to_left, to_right;

    int    edge_num;

};

int    node_cnt;

Node    tree[MAX_INTERVAL * ];

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 * ];

struct Rectangle

{

    int l, d, u, r;

}rec[MAX_REC_NUM];

int discrete[MAX_REC_NUM * ];

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 = ; 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 = ;

    interval_num = ;

    for (int i = ; 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, );

        interval[interval_num++] = Interval(d, u, r, -);

        discrete[discrete_num++] = u;

        discrete[discrete_num++] = d;

    }

}

void make_yscan()

{

    discrete_num = ;

    interval_num = ;

    for (int i = ; 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, );

        interval[interval_num++] = Interval(l, r, u, -);

        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 = ;

    proot->edge_num = ;

    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) / );

    buildtree(proot->pright, (s + e) /  + , e);

}

void recount(Node *p)

{

    if (p->num > )

    {

        p->edge_num = ;

        p->to_right = p->to_left = true;

        return;

    }

    if (p->pleft == NULL || p->pright == NULL)

    {

        p->edge_num = ;

        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 = ;

    for (int i = ; i < interval_num; i++)

    {

        int s = get_index(interval[i].start);

        int e = get_index(interval[i].end) - ;

        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 - )

            ans += (interval[i + ].pos - interval[i].pos) * line_num;

    }

    return ans;

}

int main()

{

    input();

    long long ans = ;

    make_xscan();

    sort(interval, interval + interval_num);

    discretization(discrete, discrete_num);

    buildtree(tree, , discrete_num);

    ans += work();

    make_yscan();

    sort(interval, interval + interval_num);

    discretization(discrete, discrete_num);

    buildtree(tree, , discrete_num);

    ans += work();

    printf("%lld\n", ans);

    return ;

}