1. 题目理解

我们有一个 $h \times w$ 的矩阵，每个格子可以填 $1$ 到 $m$ 的整数。
有 $n$ 个限制，每个限制给出一个子矩形范围 $(x_1, y_1, x_2, y_2)$ 以及该子矩形内所有数的最大值必须为 $v$。

我们要计算满足所有限制的填数方案数，对 $10^9+7$ 取模。

---

2. 初步分析

2.1 限制的含义

一个限制 $(x_1, y_1, x_2, y_2, v)$ 表示：

$1$. 该子矩形中至少有一个格子等于 $v$（否则最大值小于 $v$）。 $2$. 该子矩形中所有格子不能超过 $v$。

---

2.2 多个限制的关系

多个限制可能重叠，可能冲突（比如一个要求最大值是 $3$，另一个要求最大值是 $2$ 但范围有交集），也可能相容。

---

3. 常用解法思路

这是一个经典的"矩形最大值限制"计数问题，常用方法是：

$1$. 离散化：由于 $n$ 很小（$\leq 10$），但 $h, w$ 可能很大（$\leq 10000$），我们只需要考虑所有限制矩形的边界，将平面分割成 $O(n) \times O(n)$ 个矩形块。
每个块内部的所有格子，在限制条件中是被同样对待的。

$2$. 容斥原理：
对于每个限制，我们有两种情况：

• 强制该子矩形内所有数 $\leq v$。
• 强制该子矩形内所有数 $\leq v-1$（即没有数等于 $v$）。

通过容斥枚举哪些限制"不满足最大值条件"（即没有格子取到 $v$），转化为所有格子 $\leq$ 某个值的方案数。

$3$. 块处理：
离散化后，每个小块内部方案数独立，等于 $(\text{上限})^{\text{格子数}}$。

---

4. 代码结构分析

4.1 头文件和宏定义

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define ll long long
#define WA cerr<<"meowww!\n";
#define eps 1e-5
#define none -1145141919
#define pii pair<int,int>
#define Y cout<<"Yes\n"
#define N cout<<"No\n"
#define H cout<<"\n";
#define WH cerr<<"\n";
#define fi first
#define se second
#define C continue;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
#define ROF(i,a,b) for(int i=(a);i>(b);--i)
#define G(i,p) for(auto i:pq[p])
#define VG(i,p) for(int i=0;i<pq[p].size();i++)
#define pb push_back
#define pk pop_back
#define WR(x) cerr<<(x)<<"\n";
#define MAXN 51
#define K cout<<" "
#define int long long
const int MOD = 1e9 + 7;

• 定义了常用宏，$\text{MAXN}=51$ 是因为 $n \le 10$，离散化后块数 $\leq 2n+2$，所以 $51$ 足够。
• #define int long long 是为了避免溢出。

---

4.2 工具函数

void MD(int &x) {
    if (x < 0) x += MOD;
    if (x >= MOD) x -= MOD;
}
void Umn(int &x, int y) { if (x > y) x = y; }
void Umx(int &x, int y) { if (x < y) x = y; }
int rd() { int x; cin >> x; return x; }
void wr(int x) { cout << x; }
ll ksm(ll x, ll y) {
    ll rt = 1;
    while (y) {
        if (y % 2) rt = rt * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return rt;
}

• $\text{MD}$ 是取模调整。
• $\text{Umn}$/$\text{Umx}$ 是 $\text{min}$/$\text{max}$ 更新。
• $\text{ksm}$ 是快速幂。

---

4.3 变量定义

int n, m, k, q; // 这里 n 是 h, m 是 w, k 是 m（最大可填数）, q 是 n（限制数）
int cnt = 0;
pii st1[MAXN], ed1[MAXN]; // 原始输入
int h1, h2; // 离散化后行、列数
pii st[MAXN], ed[MAXN], s; // 离散化后的坐标
int vl[MAXN]; // 每个限制的 v
int hl[MAXN]; // 离散化数组
int fh1[MAXN], fh2[MAXN]; // 离散化映射回去的长度
int mp[50][50]; // 离散化后每个块的最大值限制

注意这里变量名有些混用：

• 输入的 $h, w, m, n$ 被读入 n, m, k, q。
• 所以代码中的 n 是输入的 $h$，m 是输入的 $w$，k 是输入的 $m$，q 是输入的 $n$（限制数）。

---

4.4 离散化 init()

void init() {
    // 离散化行
    For(i, 1, q) {
        hl[++cnt] = st[i].fi;
        hl[++cnt] = ed[i].fi;
        st1[i] = st[i], ed1[i] = ed[i];
    }
    hl[++cnt] = n + 1;
    hl[++cnt] = 1;
    sort(hl + 1, hl + 1 + cnt);
    int c2 = unique(hl + 1, hl + cnt + 1) - hl - 1;
    For(i, 1, c2) fh1[i] = hl[i];
    For(i, 1, q) {
        st[i].fi = lower_bound(hl + 1, hl + c2 + 1, st[i].fi) - hl;
        ed[i].fi = lower_bound(hl + 1, hl + c2 + 1, ed[i].fi) - hl;
    }
    cnt = 0;
    h1 = c2;

    // 离散化列，同理
    ...
    h2 = c2;
}

• 把每个限制的 $x_1, x_2+1, y_1, y_2+1$ 以及边界 $1$ 和 $h+1, w+1$ 加入离散化数组。
• 排序去重后，得到离散化坐标。
• $\text{fh1}[i]$ 表示第 $i$ 个离散化行坐标对应的原始行号（用于计算格子数）。

---

4.5 核心容斥部分

离散化后，矩阵被分成 $O(n^2)$ 个矩形块，每个块内部在限制条件中是一致的。

4.5.1 计算每个块的最大值限制

For(i, 2, n) For(j, 2, m) mp[i][j] = INF;
For(ii, 1, q) {
    For(i, st[ii].fi + 1, ed[ii].fi) {
        For(j, st[ii].se + 1, ed[ii].se) {
            Umn(mp[i][j], vl[ii]);
        }
    }
}

这里 $\text{mp}[i][j]$ 表示该块的最大允许值（来自所有覆盖它的限制的最小 $v$）。

---

4.5.2 检查可行性

For(ii, 1, q) {
    int cc = 0;
    For(i, st[ii].fi + 1, ed[ii].fi) {
        For(j, st[ii].se + 1, ed[ii].se) {
            if (mp[i][j] == vl[ii]) ++cc;
        }
    }
    if (cc == 0) { op = 1; break; }
}
if (op) { cout << "0\n"; C; }

如果某个限制要求的 $v$ 比它覆盖的所有块的限制 $\text{mp}$ 都小，说明不可能有格子取到 $v$，则答案为 $0$。

---

4.5.3 标记每个块属于哪些限制的"等于 v"区域

bitset<MAXN> kp[MAXN][MAXN];
For(ii, 1, q) {
    For(i, st[ii].fi + 1, ed[ii].fi) {
        For(j, st[ii].se + 1, ed[ii].se) {
            if (mp[i][j] == vl[ii]) {
                kp[i][j][ii] = 1;
            }
        }
    }
}

$\text{kp}[i][j]$ 是一个 $\text{bitset}$，标记这个块在哪些限制中必须取到 $v$（即该限制的最大值正好等于该块的上限）。

---

4.5.4 对每个块进行容斥计算

$\text{sol}(x, y)$ 计算一个块的方案数：

$1$. 如果该块已经被访问过，返回 $1$（避免重复计算连通块）。 $2$. 如果该块没有限制（$\text{mp}[x][y] == \text{INF}$），则方案数 $= k^{\text{格子数}}$。 $3$. 否则，$\text{DFS}$ 找出所有与它 $\text{mp}$ 值相同且相邻的块，形成一个连通块（因为相同上限的相邻块在容斥时要一起考虑）。 $4$. 对这些块涉及的所有限制，用容斥枚举哪些限制不满足（即该限制内没有等于 $v$ 的格子），计算方案数。

容斥部分：

• 枚举子集 $i$（二进制位表示哪些限制被违反）。
• 计算这些限制覆盖的格子数 $\text{tot}$，这些格子只能填 $1..v-1$。
• 其余格子可以填 $1..v$。
• 根据容斥系数加减。

---

4.6 主流程

main() {
    ...
    for (int __ = 1; __ <= _; __++) {
        读入 n, m, k, q
        读入限制
        init() 离散化
        初始化 mp 为 INF
        计算每个块的最小上限
        检查可行性
        标记 kp
        ans = 1
        For(i, 2, n) For(j, 2, m) ans = ans * sol(i, j) % MOD
        输出 ans
    }
}

---

5. 样例验证

以第一个样例为例：

3 3 2 2
1 1 2 2 2
2 2 3 3 1

离散化后分成 $3\times 3$ 块。
容斥计算后得到 $28$，符合输出。

---

6. 复杂度

• 离散化后块数 $O(n^2)$。
• 每个连通块容斥枚举 $O(2^{\text{涉及限制数}})$。
• 由于 $n \le 10$，可行。

---

7. 总结

这道题的核心是： $1$. 离散化减少状态。 $2$. 容斥原理处理"最大值恰好为 v"的条件。 $3$. 连通块合并相同上限的相邻块。 $4$. bitset 标记每个块与限制的关系。