N lg N planting

#include <fstream>
#include <iostream>

#include <map>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

ifstream fin("planting.in");
ofstream fout("planting.out");

struct inter {
    ll x, y1, y2;
    int d;
    inter(ll x, ll y1, ll y2, int d) : x(x), y1(y1), y2(y2), d(d) {}
    bool operator<(const inter& o) const {
        return x < o.x || (x == o.x && d > o.d);
    }
};

struct Node {
    int lo, hi;
    const vector<ll>& ys;

    Node *left;
    Node *right;
    int ct; // number of intervals [x, y) that contain [lo, hi) completely
    ll len; // measure of union of interval parts in [lo, hi) range

    int disj; // number if disjoint interval parts in [lo, hi) range
    bool abutl, abutr; // whether any interval abuts lo (or hi) side

    Node(int lo, int hi, const vector<ll>& ys) :
      lo(lo), hi(hi), ys(ys), left(0), right(0), ct(0), len(0),
      disj(0), abutl(false), abutr(false) {
        if (hi -  lo > 1) left = new Node(lo, (lo + hi) / 2, ys),
                          right = new Node((lo + hi) / 2, hi, ys);
    }

    // update (d is always just +1 or -1 in this program)
    void u(int l, int r, int d) {
        if (r <= lo || hi <= l) return;
        if (l <= lo && hi <= r) ct += d;
        else if (left) left->u(l, r, d), right->u(l, r, d);
        if (ct > 0) len = ys[hi] - ys[lo];
        else len = left ? (left->len + right->len) : 0;
        abutl = ct > 0 || (left && left->abutl);
        abutr = ct > 0 || (left && right->abutr);
        if (ct > 0) disj = 1;
        else disj = left ? (left->disj + right->disj - (left->abutr && right->abutl)) : 0;
    }

    // measure (length of union)
    ll m() const {
        return len;
    }

    // # of disjoint intervals in union
    int i() const {
        return disj;
    }
};

int main() {
    int N;
    fin >> N;

    vector<inter> ntr;
    vector<ll> ys;
    map<ll, int> yid;
    for (int i = 0; i < N; ++i) {
        ll x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        ntr.push_back(inter(x1, y2, y1, 1)), ntr.push_back(inter(x2, y2, y1, -1));
        ys.push_back(y1), ys.push_back(y2);
    }
    sort(ntr.begin(), ntr.end());
    sort(ys.begin(), ys.end()), unique(ys.begin(), ys.end());
    for (int i = 0; i < ys.size(); ++i) yid[ys[i]] = i;
    // just compressing the space of coordinates a bit

    ll area = 0, perim = 0;
    Node* seg = new Node(0, ys.size() - 1, ys);
    for (int i = 0, j = 0; i < 2 * N; i = j) {
        while (j < 2 * N && ntr[j].x == ntr[i].x && ntr[j].d > 0)
            seg->u(yid[ntr[j].y1], yid[ntr[j].y2], ntr[j].d), ++j;

        if (i == 0) perim += seg->m();
        else {
            ll total = seg->m();
            while (j < 2 * N && ntr[j].x == ntr[i].x)
                seg->u(yid[ntr[j].y1], yid[ntr[j].y2], ntr[j].d), ++j;
            perim += total - seg->m();
        }

        if (j == 2 * N) break;

        ll w = ntr[j].x - ntr[i].x;
        perim += 2 * seg->i() * w;
        area += seg->m() * w;
    }

    fout << area << "\n";

    cout << "Area: " << area << "\n";
    cout << "Perimeter: " << perim << "\n";

    return 0;
}