线段树+扫描线 HDU-1542 Picture

题目链接：[ HDU - 1828 ]

题目大意：给你n个矩形的左下角坐标和右上角坐标，求外周长。

题解

扫描线 + 离散化板子

将横竖两次扫描简化

代码如下

#include<bits/stdc++.h>
using namespace std;

const int maxn = 10010;
const int maxN = 80010;
const int INF = 0x3f3f3f3f;

inline int read(void)
{
    int w = 1, d = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        d = d * 10 + ch - '0';
        ch = getchar();
    }
    return w * d;
}

struct Node {
    int l, r, cnt;
    int lc, rc;
    int len, num;
} tree[maxN];

struct node {
    int x1, x2, y, flag;
    void init(int l, int r, int h, int f) {
        x1 = l, x2 = r, y = h, flag = f;
    }
    bool operator < (const node& a) {
        return y < a.y;
    }
} line[maxn];

int n, x1, y11, x2, y2;

void build_tree(int id, int l, int r)
{
    tree[id].l = l;
    tree[id].r = r;
    tree[id].cnt = 0;
    tree[id].len = 0;
    tree[id].lc = 0;
    tree[id].rc = 0;
    tree[id].num = 0;

    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build_tree(id << 1, l, mid);
    build_tree(id << 1 | 1, mid + 1, r);
}

void getlen(int i)
{
    if (tree[i].cnt) {
        tree[i].len = tree[i].r - tree[i].l + 1;
        tree[i].lc = tree[i].rc = 1;
        tree[i].num = 1;
    }else if (tree[i].l == tree[i].r) {
        tree[i].len = 0;
        tree[i].lc = tree[i].rc = 0;
        tree[i].num = 0;
    } else {
        tree[i].len = tree[i << 1].len + tree[i << 1 | 1].len;
        tree[i].lc = tree[i << 1].lc;
        tree[i].rc = tree[i << 1 | 1].rc;
        tree[i].num = tree[i << 1].num + tree[i << 1 | 1].num - (tree[i << 1].rc & tree[i << 1 | 1].lc);
    }
}

void update(int id, int l, int r, int v)
{
    if (tree[id].l == l && tree[id].r == r) {
        tree[id].cnt += v;
        getlen(id);
        return;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (r <= mid)
        update(id << 1, l, r, v);
    else if (l > mid)
        update(id << 1 | 1, l, r, v);
    else {
        update(id << 1, l, mid, v);
        update(id << 1 | 1, mid + 1, r, v);
    }
    getlen(id);
}


int main(void)
{
    ios::sync_with_stdio(false);
    while (~scanf("%d", &n)) {
        int minn = INF, maxx = -INF;
        for (int i = 0; i < n; i++) {
            x1 = read(), y11 = read(), x2 = read(), y2 = read();
            maxx = max(maxx, max(x1, x2));
            minn = min(minn, min(x1, x2));
            line[i].init(x1, x2, y11, 1);
            line[i + n].init(x1, x2, y2, -1);
        }
        sort(line, line + 2 * n);

        build_tree(1, minn, maxx - 1);
        long long ans = 0, last = 0;
        for (int i = 0; i < 2 * n; i++) {
            update(1, line[i].x1, line[i].x2 - 1, line[i].flag);
            ans += abs(tree[1].len - last);
            ans += (line[i + 1].y - line[i].y) * tree[1].num * 2;
            last = tree[1].len;
        }
        cout << ans << endl;
    }

    return 0;
}