思路

亚特兰蒂斯 的简化版，不同点是，前者坐标是实数，本题是整数，前者矩形个数是 $10^4$，本题是 $10^3$，不需要线段树，$O(n^2)$ 枚举就可以过。

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using LL = long long;

const int N = 2010;

int n;

struct Edge {
  int x, y1, y2, k;
  bool operator<(const Edge &e) const {
    return x < e.x;
  }
} eg[N];

struct Cover {
  int cnt;
  LL  len;
} cvr[N];

vector<int> raw;

int _int(int y) {
  return lower_bound(raw.begin(), raw.end(), y) - raw.begin();
}

LL covered_len() {
  LL ret = 0;
  for (int i = 0; i < raw.size() - 1; i++)
    if (cvr[i].cnt > 0)
      ret += cvr[i].len;
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 0, j = 0; i < n; i++) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    eg[j++] = {x1, y1, y2,  1};
    eg[j++] = {x2, y1, y2, -1};
    raw.push_back(y1);
    raw.push_back(y2);
  }
  sort(raw.begin(), raw.end());
  raw.erase(unique(raw.begin(), raw.end()), raw.end());

  for (int i = 0; i < raw.size() - 1; i++)
    cvr[i].len = raw[i + 1] - raw[i];

  n *= 2;
  sort(eg, eg + n);

  LL ans = 0;
  for (int i = 0; i < n; i++) {
    auto [x, y1, y2, k] = eg[i];
    ans += covered_len() * (x - eg[i - 1].x);

    for (int j = _int(y2); j < _int(y1); j++)
      cvr[j].cnt += k;
  }
  printf("%lld\n", ans);

  return 0;
}