扫描线求调

#include <bits/stdc++.h> 
using namespace std;
#define ls(x) x << 1
#define rs(x) x << 1 + 1 

const int maxn = 2e5 + 5;
int n, v[maxn];
struct L {
	int x, y1, y2, state;
	L() {}
	L(int a, int b, int c, int d) {
		x = a, y1 = b, y2 = c, state = d;
	}
	bool operator < (const L &oth) {
		return x < oth.x;
	}
} line[maxn];
struct Node {
	int l, r, cover;
	long long len;
} sgt[maxn << 3];

void pushup(int k) {
	if (sgt[k].cover)
		sgt[k].len = sgt[k].r - sgt[k].l;
	else
		sgt[k].len = sgt[ls(k)].len + sgt[rs(k)].len;
}
 
void build(int l, int r, int k = 1) {
	sgt[k].l = v[l], sgt[k].r = v[r];
	if (r - l <= 1) 
		return;
	int m = (l + r) >> 1;
	build(l, m, ls(k));
	build(m, r, rs(k));
}

void modify(int x, int y, int z, int k = 1) {
	int l = sgt[k].l, r = sgt[k].r;
	if (x <= l && y >= r) {
		sgt[k].cover += z;
		pushup(k);
		return;
	}
	if (x < sgt[ls(k)].r)
		modify(x, y, z, ls(k));
	else if (y > sgt[rs(k)].l) 
		modify(x, y, z, rs(k));
	pushup(k);
} 
 
int main() {
	scanf("%d", &n); 
	for (int i = 1; i <= n; i++) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		v[i] = b, v[n + i] = d;
		line[i] = L(a, b, d, 1), line[n + i] = L(c, b, d, -1);
	}
	sort(v + 1, v + (n << 1) + 1);
	sort(line + 1, line + (n << 1) + 1);
	build(1, n << 1);
	unsigned long long ans = 0;
	for (int i = 1; i <= (n << 1); i++) {
		ans += sgt[1].len * (line[i].x - line[i - 1].x);
//		printf("%llu %d %d %d\n", ans, sgt[1].len, line[i].x, line[i - 1].x);
		modify(line[i].y1, line[i].y2, line[i].state);
	}
    printf("%llu", ans);
}