题目链接
题解
矩阵面积的并模板。（请求洛谷加为模板题）
很明显是要离散化的。
我们将矩阵与\(x\)轴平行的两个线段取出来。并且将这两个端点的\(x1\)和\(x2\)进行离散化。
因为每一次我们都会对当前的这一层的某一段线段进行操作，那么就用权值线段树维护是否存在。
这个只是矩阵面积的并。
还有加强版：【HDU 1542】
还有矩阵面积的交。
代码
#include <bits/stdc++.h>
#define gc getchar
#define lc (nod << 1)
#define rc (nod << 1 | 1)
using namespace std;
typedef long long ll;
const int N = 2003;
template <typename T> void read(T &x) {
x = 0; T fl = 1; char c = 0;
for (; c < '0' || c > '9'; c = gc())
if (c == '-') fl = -1;
for (; c >= '0' && c <= '9'; c = gc())
x = (x << 1) + (x << 3) + (c ^ 48);
x *= fl;
}
struct E{ int l, r, h, d; } ed[N * 2];
bool cmp_sl(E x, E y) { return x.h < y.h; }
ll ans = 0ll;
int n, dcnt;
int disc[N];
struct seg { ll s, tag; } tr[N << 2];
void pushup(int nod, int l, int r) {
if (tr[nod].tag) tr[nod].s = disc[r + 1] - disc[l];
else if (l == r) tr[nod].s = 0;
else tr[nod].s = tr[lc].s + tr[rc].s;
}
void upd(int nod, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr) {
tr[nod].tag += val;
pushup(nod, l, r);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) upd(lc, l, mid, ql, qr, val);
if (qr > mid) upd(rc, mid + 1, r, ql, qr, val);
pushup(nod, l, r);
}
int main() {
read(n);
for (int i = 1, x1, y1, x2, y2; i <= n; i ++) {
read(x1); read(y1); read(x2); read(y2);
disc[++ dcnt] = x1; ed[dcnt] = (E){x1, x2, y1, 1};
disc[++ dcnt] = x2; ed[dcnt] = (E){x1, x2, y2, -1};
}
sort(disc + 1, disc + 1 + dcnt);
sort(ed + 1, ed + 1 + dcnt, cmp_sl);
int m = unique(disc + 1, disc + 1 + dcnt) - disc - 1;
for (int i = 1; i < dcnt; i ++) {
int l = lower_bound(disc + 1, disc + 1 + m, ed[i].l) - disc;
int r = lower_bound(disc + 1, disc + 1 + m, ed[i].r) - disc;
if (l < r) upd(1, 1, m, l, r - 1, ed[i].d);
ans += tr[1].s * (ed[i + 1].h - ed[i].h);
}
cout << ans << endl;
return 0;
}