P5490 如题

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
int n, x1, y, x2, y2, tot, p[MAXN << 1];
long long ans;
struct Line {
	int y, x1, x2, flag;
} line[MAXN << 1];
struct Node {
	int sum, len;
} d[MAXN << 3];
bool cmp(Line a, Line b) {
	return a.y < b.y;
}
void pushup(int u, int l, int r) {
	if(d[u].sum) {
        d[u].len = p[r + 1] - p[l];
    } else if(l == r) {
    	d[u].len = 0;
	} else {
        d[u].len = d[u << 1].len + d[u << 1 | 1].len;
    }
}
void upd(int u, int l, int r, int i, int j, int x) {
	if(i <= p[l] && p[r + 1] <= j) {
		d[u].sum += x;
        pushup(u, l, r);
		return;
	}
	int mid = l + r >> 1;
	if(i < p[mid + 1]) {
        upd(u << 1, l, mid, i, j, x);
    }
	if(j > p[mid + 1]) {
        upd(u << 1 | 1, mid + 1, r, i, j, x);
    }
	pushup(u, l, r);
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> x1 >> y >> x2 >> y2;
		p[i] = x1;
        p[i + n] = x2;
		line[i].y = y;
        line[i + n].y = y2;
		line[i].x1 = x1;
        line[i + n].x1 = x1,
		line[i].x2 = x2,
        line[i + n].x2 = x2,
		line[i].flag = 1,
        line[i + n].flag = -1;
    }
	sort(p + 1, p + (n << 1) + 1);
	tot = unique(p + 1, p + (n << 1) + 1) - p - 1;
	sort(line + 1, line + (n << 1) + 1, cmp);
	for(int i = 1; i < n << 1; i++)
		upd(1, 1, tot - 1, line[i].x1, line[i].x2, line[i].flag),
		ans += (long long)(line[i + 1].y - line[i].y) * d[1].len;
    cout << ans;
	return 0;
}