题目分析

给定 $H \times W$ 的网格，每个格子有互不相同的高度。
统计所有恰好覆盖一个子矩形且路径严格单调下降的路径数量。

---

核心思路

1. 问题转化

"恰好覆盖一个子矩形"意味着路径必须填满某个矩形区域的所有格子，且路径是单调下降的。

2. 关键观察

• 由于高度互不相同，路径在矩形中必须是哈密顿路径（经过每个格子恰好一次）
• 矩形必须满足：从最高点到最低点存在一条单调路径遍历所有格子
• 对于 $1 \times k$ 或 $k \times 1$ 的矩形，任何单调路径都满足条件

3. 解法框架

第一部分：一维情况

对于 $1 \times m$ 或 $n \times 1$ 的矩形，直接统计：

• 从左到右的单调递增/递减连续子数组
• 从上到下的单调递增/递减连续子数组

// 统计行内的单调连续子数组
ott(i, 1, n) {
    ott(j, 1, m) {
        s[j] = 1;
        if (a[i][j - 1] < a[i][j]) s[j] += s[j - 1];
        ans += s[j];
    }
    // 类似处理递减情况...
}

第二部分：二维矩形验证

对于 $2 \times 2$ 及以上的矩形，需要验证是否存在哈密顿单调路径。

---

算法实现详解

1. 预处理

方向编码

int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};  // 上下左右

find 函数：关键验证函数

int find(int x, int y, int ban = 0) {
    // 检查从(x,y)出发，在不禁用某些方向时能否形成单调路径
    // 返回 inf 表示可以形成路径，否则返回高度差
}

• ban 参数用位掩码表示禁用的方向（1:左, 2:右, 4:上, 8:下）
• 检查是否存在从当前格子出发的单调下降路径

2. 前缀和数组

b[i][j] = b[i-1][j] + find(i, j)           // 列方向前缀和
c[i][j] = c[i][j-1] + find(i, j, 1)        // 行方向，禁用左
d[i][j] = d[i][j-1] + find(i, j, 2)        // 行方向，禁用右  
e[i][j] = e[i-1][j] + find(i, j, 4)        // 列方向，禁用上
f[i][j] = f[i-1][j] + find(i, j, 8)        // 列方向，禁取下

3. 二维矩形统计

枚举所有可能的矩形 [xl, xr] × [1, m]，使用哈希表统计满足条件的矩形：

ott(xl, 1, n) {
    ott(xr, xl + 1, n) {
        ott(i, 1, m) {
            // 计算关键值，用哈希表匹配
            ans += S[key1];
            ++ S[key2];
        }
        S.clear();
    }
}

关键值计算基于：

• 边界格子的连通性检查
• 内部格子的单调路径存在性
• 使用前缀和快速计算

---

复杂度分析

• 一维部分：$O(nm)$
• 二维部分：$O(n^2 m)$
• 由于 $n \times m \leq 50000$ 且 $n \leq m$，实际可接受

---

算法标签

主要算法：

• 动态规划（一维统计）
• 前缀和
• 哈希表
• 枚举优化

相关技巧：

• 方向位掩码
• 网格图处理
• 组合计数

---

代码亮点

1. 转置优化：当 $n > m$ 时转置矩阵，保证 $n \leq m$
2. 位掩码方向控制：用 ban 参数灵活控制路径方向
3. 前缀和加速：预处理各种方向的条件和
4. 哈希匹配：快速统计满足条件的矩形对

---

总结

这道题通过分类讨论巧妙解决：

• 一维情况直接DP统计
• 二维情况通过枚举+验证，利用前缀和和哈希表优化

核心在于理解"恰好覆盖子矩形"与"单调哈密顿路径"的等价关系，以及如何高效验证这种路径的存在性。