思路与算法

先把每个最大值等式拆为所有格≤v且至少一格等于v。容斥枚举哪些矩形缺少等于v的格，把它们的上界降成v-1。按矩形边界压缩坐标；每块的原最低上界cap和提供该上界的约束mask固定，只有被容斥选中的约束与这个mask相交时cap才再降1。聚合同(cap,mask)面积，每个容斥项为各块允许值数的面积次幂之积。

正确性说明

坐标块中所有格受到完全相同的上界集合，原最低上界充分决定其取值范围。把某个更大上界降1不会低于已有较小上界，故仅最低约束的选择影响块，判mask相交准确。格子独立选值，相乘计数；容斥恰排除每个等式中没有最大值的违规事件。

复杂度

边界≤2n+2，分块及判约束O(n³)，块数G=O(n²)，2^n容斥各做G次模幂O(Glog(hw))，总O(n³+2^n n²log(hw))时间，空间O(n²)。T≤5逐组处理。

易错点

面积必须按原坐标差计算，不能按压缩格数计。上界降为0时正面积块方案0。重复约束和矛盾约束均通过容斥自动处理。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long pw(long long a, long long n) {
    long long r = 1;
    while (n) {
        if (n & 1)
            r = r * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int h, w, m, n;
        cin >> h >> w >> m >> n;
        vector<array<int, 5>> q(n);
        vector<int> X = {1, h + 1}, Y = {1, w + 1};
        for (auto &a : q) {
            for (int &x : a)
                cin >> x;
            X.push_back(a[0]);
            X.push_back(a[2] + 1);
            Y.push_back(a[1]);
            Y.push_back(a[3] + 1);
        }
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());
        sort(Y.begin(), Y.end());
        Y.erase(unique(Y.begin(), Y.end()), Y.end());
        map<pair<int, int>, long long> groups;
        for (int i = 0; i + 1 < (int)X.size(); i++)
            for (int j = 0; j + 1 < (int)Y.size(); j++) {
                int cap = m, mask = 0;
                for (int z = 0; z < n; z++)
                    if (q[z][0] <= X[i] && X[i] <= q[z][2] && q[z][1] <= Y[j] && Y[j] <= q[z][3])
                        cap = min(cap, q[z][4]);
                for (int z = 0; z < n; z++)
                    if (q[z][4] == cap && q[z][0] <= X[i] && X[i] <= q[z][2] && q[z][1] <= Y[j] &&
                        Y[j] <= q[z][3])
                        mask |= 1 << z;
                groups[{cap, mask}] += 1LL * (X[i + 1] - X[i]) * (Y[j + 1] - Y[j]);
            }
        long long ans = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            long long ways = 1;
            for (auto x : groups) {
                int cap = x.first.first - ((x.first.second & mask) != 0);
                ways = ways * pw(cap, x.second) % MOD;
            }
            if (__builtin_popcount((unsigned)mask) & 1)
                ans = (ans - ways + MOD) % MOD;
            else
                ans = (ans + ways) % MOD;
        }
        cout << ans << '\n';
    }
}