ある \(1\leq i\leq N\) について\(A_i=x\) または \(C_i=x\) をみたすような \(x\) を昇順に並べたものを \(x_1\) , \(x_2\) , \(\ldots\) , \(x_{k_x}\) とし、同様に、\(B_i=y\) または \(D_i=y\) をみたすような \(y\) を昇順に並べたものを \(y_1\) , \(y_2\) , \(\ldots\) , \(y_{k_y}\) とします。
また、 \([X_1,X_2]\) で実直線上の区間を表し、 \([X_1,X_2]\times [Y_1,Y_2]\) で \((X_1,Y_1)\) , \((X_2,Y_1)\) , \((X_1,Y_2)\) , \((X_2,Y_2)\) を頂点とする長方形領域を表すとします。

このとき、\([x_1, x_{k_x}]\times [y_1, y_{k_y}]\)以外の領域はどのクエリにおいても色が反転させられることはなく白色のままなのでこの範囲についてのみ考えれば良いです。さらに、 \([x_i, x_{i+1}]\times [y_i, y_{i+1}]\) の各領域についてその領域内の色は一定なのでこの部分についてはまとめて考えることができます。 しかし、この時点までの考察を踏まえて、これを愚直に書くと \(\Theta(Q^3)\) 、 累積和等を使っても \(\Theta(Q^2)\) となり時間がかかりすぎてしまいます。

そこで \(i\) について昇順に \([x_j, x_{j+1}]\times [y_i, y_{i+1}]\)が最終的に黒く塗られているような \([x_j,x_{j+1}]\) の長さの総和 \(S_i\) を求め、 \(\sum_{i=1}^{k_y-1} (y_{i+1}-y_i)S_i\) として答えを求めることを考えます。 \(S_{i-1}\) と \(S_i\) の違いは \(B_k=y_i\) または \(D_k=y_i\) となるクエリによる影響だけです。これらの更新は遅延セグ木によって行う事が出来ます。 \(j\) 番目の要素は \(x_{j+1}-x_j\) または \(0\) の値を取り、ある範囲内の要素の値を一方から他方へ変更する区間変更クエリと全体の総和をとるクエリの \(2\) つを実装すればよいです。

変更クエリは \(1\) 回あたり \(O(\log Q)\) 、 総和クエリは全体を取るものしかないので \(1\) 回あたり \(O(1)\) でそれぞれ実行でき、どちらも \(O(Q)\) 回しか実行されないため、全体で \(O(Q\log Q)\) であり、この問題を解く事が出来ました。

C++による実装例:

#include <bits/stdc++.h>

using namespace std;

#define N (1<<18)
#define INF (int)2e+9
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep3(i, a, b) for(int i = a; i >= b; --i)
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define pii pair<int,int>

int le, ri;
int l[(2 * N)];
int r[(2 * N)];
int len[(2 * N)];
int seg[(2 * N)];
bool laz[(2 * N)];

int change(int k) {
	if (laz[k]) {
		seg[k] = len[k] - seg[k];
		if (k < N) {
			laz[(2 * k)] = (!laz[(2 * k)]);
			laz[(2 * k) + 1] = (!laz[(2 * k) + 1]);
		}
		laz[k] = false;
	}
	if ((ri <= l[k]) || (r[k] <= le))return seg[k];
	if ((le <= l[k]) && (r[k] <= ri)) {
		laz[k] = true;
		return (len[k] - seg[k]);
	}
	int retl = change(2 * k);
	int retr = change(2 * k + 1);
	return seg[k] = retl + retr;
}


int main(void) {
	int n, m;
	vector<pair<int, pii> >q;
	vector<int>cx;
	map<int, int>mp;
	int a, b, c, d, pre;
	ll x, y, ans;

	cin >> n;
	rep(i, n) {
		cin >> a >> b >> c >> d;
		cx.pb(a);
		cx.pb(c);
		q.pb({ b,{a,c} });
		q.pb({ d,{a,c} });
	}

	sort(all(cx));
	unique(all(cx));
	m = cx.size();
	rep(i, m)mp[cx[i]] = i;
	rep(i, N) {
		l[N + i] = i;
		r[N + i] = i + 1;
		if (i < m - 1)len[N + i] = cx[i + 1] - cx[i];
		else len[N + i] = 0;
		seg[N + i] = 0;
		laz[N + i] = false;
	}
	rep3(i, N - 1, 1) {
		l[i] = l[2 * i];
		r[i] = r[2 * i + 1];
		len[i] = len[2 * i] + len[2 * i + 1];
		seg[i] = 0;
		laz[i] = false;
	}

	ans = 0;
	pre = INF;
	sort(all(q));
	n = q.size();
	rep(i, n) {
		if (pre < q[i].first) {
			x = (ll)(q[i].first - pre);
			y = (ll)seg[1];
			ans += (x*y);
		}
		pre = q[i].first;

		le = mp[q[i].second.first];
		ri = mp[q[i].second.second];
		change(1);
	}
	cout << ans << endl;
	return 0;
}