Linkkkkkkkkkkkk

这其实是个dp问题

可以拆成一个个dp小问题，然后求和，这个小问题就是以$(i,j)$为右下角方块下会有多少矩形，然后把每一个位置加起来就行了。

应注意到以下命题充要性成立:如果$(i,j)$位置存在一个正方形长度为n满足题意，那么在$(i-1,j),(i,j-1),(i-1,j-1)$处都应存在着长度为 n-1的矩形满足题意

这样就可以进行dp了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int ma[3001][3001];
int h,n,m;
int dp[3001][3001];
int x,y;
long long ans;
int main(){
    scanf("%d%d%d",&n,&m,&h);
    for(int i=1;i<=h;++i){
        scanf("%d%d",&x,&y);
        ma[x][y]=1;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(ma[i][j]) dp[i][j]=0;
            else dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
            ans+=dp[i][j];
        }
    }
    cout<<ans;
    return 0;
}