【链接】
https://nanti.jisuanke.com/t/30991
【题意】
求不包含黑点的子矩阵个数
【思路】
先简化一下问题，没有黑点，求子矩阵的个数：枚举高度，枚举底的左界和右界，求和。
升级+黑点：在求子矩阵的基础上维护一个高度的最小值，同时用一个变量数组维护一下最小高度。
【总结】
要善于抽离出基本的数学思想
【代码】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
int a[maxn][105];
int mi[maxn];int main() {int n, m, k;int t;scanf("%d", &t);int ca = 0;while (t--) {scanf("%d%d%d", &n, &m, &k);memset(a, 0, sizeof(a));memset(mi, 0, sizeof(mi));while (k--) {int x, y;scanf("%d%d", &x, &y);a[x][y] = 1;}ll ans = 0;for (int h = 1; h <= n; h++) {for (int i = 1; i <= m; i++)if (a[h][i]) {mi[i] = h;}for (int i = 1; i <= m; i++) {int minn = inf;for (int j = i; j <= m; j++) {minn = min(minn, h - mi[j]);ans += minn;}}}cout <<"Case #"<<++ca<<": " <<ans << endl;}
}