矩形并的周长的板子

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1e4 + 5;

struct Point//左下&右上
{
    int h, l, r, f;
    Point(int _h, int _l, int _r, int _f): h(_h), l(_l), r(_r), f(_f) {};
};
vector<Point> que1, que2;
vector<int> vx, vy;

struct Tree
{
    int left[MAXN * 8], right[MAXN * 8], cnt[MAXN * 8], part[MAXN * 8];
    void insert(int s, int l, int r, int ll, int rr, int delta)
    {
        if(l == ll && r == rr)
        {
            cnt[s] += delta;
            if(cnt[s])
            {
                part[s] = left[s] = right[s]= 1;
            }
            else if(ll != rr)
            {
                part[s] = part[s * 2] + part[s * 2 + 1]
                        - (right[s * 2] && left[s * 2 + 1]);
                left[s] = left[s * 2];
                right[s] = right[s * 2 + 1];
            }
            else part[s] = left[s] = right[s] = 0;
            return;
        }
        int m = (l + r) / 2;
        if(rr <= m) insert(s * 2, l, m, ll, rr, delta);
        else if(ll > m) insert(s * 2 + 1, m + 1, r, ll, rr, delta);
        else
        {
            insert(s * 2, l, m, ll, m, delta);
            insert(s * 2 + 1, m + 1, r, m + 1, rr, delta);
        }
        if(!cnt[s])
        {
            part[s] = part[s * 2 + 1] + part[s * 2] - (right[s * 2] && left[s * 2 + 1]);
            left[s] = left[s * 2];
            right[s] = right[s * 2 + 1];
        }
    }
} t;

bool cmp(const Point &a, const Point &b)
{
    if(a.h == b.h) return a.f > b.f;
    return a.h < b.h;
}

vector<int> _x1, _y1, _x2, _y2;
int solve(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2)
{
    int n = x1.size(), ans = 0;
    for(int i = 0; i < n; ++i)
    {
        vx.push_back(x1[i]);
        vy.push_back(y1[i]);
        vx.push_back(x2[i]);
        vy.push_back(y2[i]);
    }
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    for(int i = 0; i < n; ++i)
    {
        x1[i] = lower_bound(vx.begin(), vx.end(), x1[i]) - vx.begin();
        x2[i] = lower_bound(vx.begin(), vx.end(), x2[i]) - vx.begin();
        y1[i] = lower_bound(vy.begin(), vy.end(), y1[i]) - vy.begin();
        y2[i] = lower_bound(vy.begin(), vy.end(), y2[i]) - vy.begin();
        que1.push_back(Point(y1[i], x1[i], x2[i], 1));
        que1.push_back(Point(y2[i], x1[i], x2[i], -1));
        que2.push_back(Point(x1[i], y1[i], y2[i], 1));
        que2.push_back(Point(x2[i], y1[i], y2[i], -1));
    }
    sort(que1.begin(), que1.end(), cmp);
    sort(que2.begin(), que2.end(), cmp);

    for(int i = 0, j; i < (int)que1.size(); i = j)
    {
        for(j = i; j < (int)que1.size() && que1[j].h == que1[i].h; ++j)
            t.insert(1, 0, vx.size(), que1[j].l, que1[j].r - 1, que1[j].f);
        if(que1[i].h + 1 < (int)vy.size())
            ans += t.part[1] * 2 * (vy[que1[i].h + 1] - vy[que1[i].h]);
    }
    for(int i = 0, j; i < (int)que2.size(); i = j)
    {
        for(j = i; j < (int)que2.size() && que2[j].h == que2[i].h; ++j)
            t.insert(1, 0, vy.size(), que2[j].l, que2[j].r - 1, que2[j].f);
        if(que2[i].h + 1 < (int)vx.size())
            ans += t.part[1] * 2 * (vx[que2[i].h + 1] - vx[que2[i].h]);
    }
    return ans;
}

int main()
{
    int n;
    int a, b, c, d;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        _x1.push_back(a);
        _y1.push_back(b);
        _x2.push_back(c);
        _y2.push_back(d);
    }
    printf("%d\n", solve(_x1, _y1, _x2, _y2));
}