[捞贴] (https://www.luogu.com.cn/discuss/show/283648)

本蒟蒻 20 分代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define For(i,a,b) for(ll i = a ; i <= b ; i ++)
#define FoR(i,a,b) for(ll i = a ; i >= b ; i --)
typedef long long ll;
typedef double dl;
ll MAX(ll x , ll y) {return (x > y) ? x : y;}
ll MIN(ll x , ll y) {return (x < y) ? x : y;}

const int MAXN = 1e5 + 123; 

using namespace std;

inline int Read() {
	register int x = 0;
	bool flag = false;
	register char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			flag = true;
		ch = getchar();
	}
	if (flag) {
	    while ('0' <= ch && ch <= '9') {
	   		 x = x * 10 - ch + '0';
			 ch = getchar();
	    }
	}
	else {
        while ('0' <= ch && ch <= '9') {
	   		 x = x * 10 + ch - '0';
			 ch = getchar();
	    }
	}
	return x;
}

ll N;
struct rectangle{
	ll x1 , x2;
	ll y0;
	ll val;
	bool operator < (rectangle b) {
		return y0 < b.y0;
	}
}a[MAXN << 1 | 1]; 
ll x[MAXN] , tpx;

void input() {
	N = Read();
	For (i , 1 , N) {
		x[++ tpx] = a[i].x1 = a[i + N].x1 = Read();
		a[i].y0 = Read();
		x[++ tpx] = a[i].x2 = a[i + N].x2 = Read();
		a[i + N].y0 = Read();
		a[i].val = -1;
		a[i + N].val = 1;
	}
	sort(x + 1 , x + tpx + 1);
	tpx = unique(x + 1 , x + tpx + 1) - x - 1;
	For (i , 1 , N) {
		a[i].x1 = a[i + N].x1 = lower_bound(x + 1 , x + tpx + 1 , a[i].x1) - x;
		a[i].x2 = a[i + N].x2 = lower_bound(x + 1 , x + tpx + 1 , a[i].x2) - x;
		//printf ("%d %d\n" , a[i].x1 , a[i].x2);
	}
	sort(a + 1 , a + (N << 1 | 1));
}

ll ans = 0;
struct segment_tree{
	ll cnt , len;
}e[MAXN << 4 | 1];

void modify(ll o , ll l , ll r , ll ql , ll qr , ll val) {
	if (ql <= l && r <= qr) {
		e[o].cnt += val;
		if (e[o].cnt)
			e[o].len = x[r + 1] - x[l];
		else
			e[o].len = e[o << 1].len + e[o << 1 | 1].len;
		return;
	}
	ll mid = (l & r) + ((l ^ r) >> 1);
	if (ql <= mid)
		modify(o << 1 , l , mid , ql , qr , val);
	if (qr > mid)
		modify(o << 1 | 1 , mid + 1 , r , ql , qr , val);
		
	if (e[o].cnt)
		e[o].len = x[r + 1] - x[l];
	else
		e[o].len = e[o << 1].len + e[o << 1 | 1].len;
}

void solve() {
	For (i , 1 , (N << 1) - 1) {
		modify(1 , 1 , tpx - 1 , a[i].x1 , a[i].x2 - 1 , a[i].val);
		ans += (a[i + 1].y0 - a[i].y0) * e[1].len;
	}
	printf ("%lld\n" , ans);
}

int main() {
	input();
	solve();
    return 0;
}

MAXN 改为 1e6 + 123 就 AC 了。