统计子矩阵

给定一个 $N \times M$ 的矩阵 $A$，请你统计有多少个子矩阵 (最小 $1 \times 1$，最大 $N × M$) 满足子矩阵中所有数的和不超过给定的整数 $K$?

输入格式

第一行包含三个整数 $N, M$ 和 $K$。

之后 $N$ 行每行包含 $M$ 个整数，代表矩阵 $A$。

输出格式

一个整数代表答案。

数据范围

对于 $30\%$ 的数据，$N, M ≤ 20$，
对于 $70\%$ 的数据，$N, M ≤ 100$，
对于 $100\%$ 的数据，$1 ≤ N, M ≤ 500; 0 ≤ A_{ij} ≤ 1000; 1 ≤ K ≤ 2.5 \times 10^8$。

输入样例：

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

输出样例：

19

样例解释

满足条件的子矩阵一共有 $19$，包含：

• 大小为 $1 × 1$ 的有 $10$ 个。
• 大小为 $1 × 2$ 的有 $3$ 个。
• 大小为 $1 × 3$ 的有 $2$ 个。
• 大小为 $1 × 4$ 的有 $1$ 个。
• 大小为 $2 × 1$ 的有 $3$ 个。

解题思路

  参考 [COCI2021-2022#6] Zemljište 中枚举子矩阵的方法，即枚举子矩阵的上边界、下边界、右边界，然后通过二分或双指针来确定左边界，这样时间复杂度就能做到 $O(n^3 \log{n})$ 或 $O(n^3)$。记录这两题主要想告诉自己，枚举子矩阵不要总是那么死板去想着枚举左上角和右下角两个坐标。

  下面给出双指针做法的正确性证明就可以了。首先矩阵中的元素均是非负整数，因此当确定了子矩阵的上边界 $x_1$，下边界 $x_2$，右边界 $y_2$ 后，随着 $y_1$ 增加（向右移动），那么构成的矩阵 $(x_1, y_1, x_2, y_2)$ 的和也会递减，因此满足单调性。假设此时左边界 $y_1$ 是满足构成矩阵和不超过 $k$ 的最靠左的位置，那么当 $y_2$ 向右移动到 $y_2'$，$y_1$ 只会向右移动。否则假设 $y_1$ 向左移动到 $y_1'$，由于矩阵 $(x_1, y_1', x_2, y_2')$ 的和不超过 $k$，因此矩阵 $(x_1, y_1', x_2, y_2)$ 的和也不超过 $k$，而 $y_1' < y_1$，这就与假设矛盾了。

  AC 代码如下，时间复杂度为 $O(n^3)$：

#include <bits/stdc++.h>
using namespace std;

const int N = 510;

typedef long long LL;

int s[N][N];

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &s[i][j]);
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    LL ret = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            for (int u = 1, v = 1; u <= m; u++) {
                while (v <= u && s[j][u] - s[i - 1][u] - s[j][v - 1] + s[i - 1][v - 1] > k) {
                    v++;
                }
                ret += u - v + 1;
            }
        }
    }
    printf("%lld", ret);
    
    return 0;
}

参考资料

  AcWing 4405. 统计子矩阵（秋招每日一题）：https://www.acwing.com/video/4234/