题目链接：https://nanti.jisuanke.com/t/A1948
题目大意：给你一个n * m的矩阵。有k个黑块。问有多少个不包含黑块的矩阵。
()
图片说明

思路：时间给你2秒。我们考虑n * m * m的写法。枚举每个点作为右下角。再枚举矩阵的宽。
图片说明
如图：以右下角0号点为矩阵的右下角的矩阵个数。枚举x。为矩阵的左边界。如图0和0-4都会产生一个矩形。ans+=H
图片说明
枚举x到前一个位置。如图0和1-5都会产生一个矩形。ans+=H
图片说明
枚举x到前一个位置。如图0和1-3都会产生一个矩形。ans+=H
图片说明
枚举x到前一个位置。如图0和1-3都会产生一个矩形。ans+=H

枚举x到前一个位置。如图0和1-2都会产生一个矩形。ans+=H
图片说明
枚举x到前一个位置。如图0和1-2都会产生一个矩形。ans+=H

H[i]=第i列离垂直方向上第一个黑色块的距离。我们边枚举边计算H[i]就可以了。如果(x, y)是黑块.mx[y]=x。H[i]=i-mx[i]+1。

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

int hs[100005][105], mx[105];
vector<int> v;
int main(){

    int T, cas=1; scanf("%d", &T);
    while(T--){
        memset(mx, 0, sizeof(mx));
        int n, m, k, x, y; scanf("%d%d%d", &n, &m, &k);
        for(int i=1; i<=k; i++){
            scanf("%d%d", &x, &y);
            hs[x][y]=1;
            v.push_back(x);
            v.push_back(y);
        }
        LL ans=0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(hs[i][j]){
                    mx[j]=i;
                }
            }
            for(int j=1; j<=m; j++){
                int h=i;
                for(int k=j; k>0; k--){
                    h=min(h, i-mx[k]);
                    ans+=h;
                }
            }
        }
        for(int i=0; i<v.size(); i+=2){
            hs[v[i]][v[i+1]]=0;
        }
        printf("Case #%d: %lld\n",cas++, ans);
    }

    return 0;
}