Solution

扫描线
读题的时候发现重点是，这就大大简化了这道题。
首先我们先考虑如何计算某一行的贡献，我们发现如果我们知道连续的白色块的，那么他的贡献就是，那么我们创建一个set<pair<int, int>>去维护当前行的连续白色格子的断点即可，我们对每一列的计算可以将列旋转90度看作行来处理，将改为互换即可。需要注意的是当的时候，两次扫描的结果都是的格子，是一样的，所以只需要横竖里任选一遍扫描即可。
扫描线同理，标记入边操作和出边操作，进行排序之后维护。
del：入边的时候插入黑色格子，即删去set中的（若存在），这点和珂朵莉树很相像。
add:出边的时候我们插入之前被删去的，合并格子，这里需要注意，排序的时候是先根据h从低到高，同时del操作排在后面，这样就比会避免先删后加，删的时候还没有加进去的问题。合并操作即先看下左边是否能合并，是否存在，再看下右边是否存在然后将其都删去，更新并插入即可。

Code

#include <bits/stdc++.h>

#define l first
#define r second
#define mp make_pair
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LNINF = 0xc0c0c0c0c0c0c0c0;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 1e6 + 5;

int n, w, h, c, m, cnt1, cnt2;
ll ans, res;

struct node {
    int l, r, h, op;

    inline bool operator <(const node & T) const {
        return h == T.h ? op < T.op : h < T.h;
    }
} a[N], b[N];

set<pair<int, int>> s;

void dw(int l, int r) {
    res -= max(r - l + 2 - m, 0);
}

void update(int l, int r) {
    s.insert({l, r});
    res += max(r - l + 2 - m, 0);
}

void del(int l, int r) {
    auto k = s.lower_bound({l, r});
    if (k == s.end() || k->l > r) k--;
    auto [L, R] = *k;
    s.erase(k);
    dw(L, R);
    if (L < l) update(L, l - 1);
    if (R > r) update(r + 1, R);
}

void add(int l, int r) {
    auto k = s.lower_bound({l, r});
    if ((!s.empty() && k != s.begin())) {
        k--;
        if (k->r == l - 1) {
            l = k->l;
            dw(k->l, k->r);
            s.erase(k);
        }
    }
    k = s.lower_bound({l, r});
    if (k != s.end()) {
        if (k->l == r + 1) {
            r = k->r;
            dw(k->l, k->r);
            s.erase(k);
        }
    }
    update(l, r);
}

void solve(int n, int x, node *a, int cnt) {
    s.clear();
    sort(a + 1, a + 1 + cnt);
    res = 0;
    a[0] = {1, n, 1, 0};
    a[cnt + 1].h = x + 1;
    for (int i = 0; i <= cnt; ) {
        int h = a[i].h;
        while (i <= cnt && h == a[i].h) {
            if (a[i].op == 1) del(a[i].l, a[i].r);
            else add(a[i].l, a[i].r);
            i++;
        }
        ans += res * (a[i].h - h);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> w >> h >> n >> c >> m;
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        a[++cnt1] = {x1, x2, y1, 1};
        a[++cnt1] = {x1, x2, y2 + 1, 0};
        b[++cnt2] = {y1, y2, x1, 1};
        b[++cnt2] = {y1, y2, x2 + 1, 0};
    }
    solve(w, h, a, cnt1);
    if (m != 1) solve(h, w, b, cnt2);
    cout << ans << '\n';

    return 0;
}