看到官方题解是 \(O(n^2)\) 的 dp。
提供一个 \(O(n^2 \log_2 n)\) 的做法，考场思路，大概比较简单。
Description
给一个 \(H\) 行 \(W\) 列的网格，其中一些点被涂成黑色，求整个正方形内都未被涂黑的正方形的个数。
Solution
考场上首先想到的简单暴力做法，即枚举正方形左上角端点，然后枚举正方形边长，求目前枚举的正方形中有没有黑色格子。
这样做是 \(O(n^3)\) 的，接受不了。
所以我们需要减少或者优化掉一维的枚举。
考虑固定正方形的左上角，先 \(O(n^2)\) 枚举左上角 \((i,j)\)，然后考虑如何快速计算答案。
显然对于满足条件的正方形，其内部黑色格子的数量是 \(0\)，而在暴力枚举的过程中，正方形的边长不断增大，黑色格子的数量是单调不减的。
因此，如果以 \((i,j)\) 为左上角端点，边长为 \(len\) 的正方形中黑格个数 \(> 0\)，那么左上端点不变，边长 \(\geq len\) 的正方形中黑格个数一定 \(> 0\)，不可行。
而如果以 \((i,j)\) 为左上角端点，边长为 \(len\) 的正方形中黑格个数 \(= 0\)，那么左上角不变，边长 \(\leq len\) 的正方形中黑格个数也一定 \(= 0\)，可行。
换句话说，设 \(a_{len}\) 表示以 \((i,j)\) 为左上角的正方形中，边长为 \(len\) 的，其内部黑色格子的数量，那 \(a_{len}\) 随 \(len\) 单调不减，而我们要求出 \(a\) 数组前面连续的 \(0\) 的个数。
这满足单调性，可以二分边长 \(len\) ，对于每一个二分到的 \(len\) ，可以用二维前缀和 \(O(1)\) 算出正方形内黑色格子数。
不会二维前缀和的同学可以看一下 P2004。
总复杂度 \(O(n^2 \log_2 n)\) ，此处的 \(n\) 即题目里的 \(H\),\(W\), \(3000\) 级别的，勉强可以过，最慢的点 \(528 ms\)。
Code
里面有一些注释。
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x==0){
putchar('0'); return ;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
template<typename T> inline void read(T &x){
x=0; int w=1; char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1; ch=getchar();
}
while(isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=w; return ;
}
}
using namespace IO; //快读
#define writesp(x) write(x),putchar(' ')
#define writeln(x) write(x),putchar('\n')
#define inf 0x3f3f3f3f3f3f
#define mod 998244353
#define maxn 3010
#define int long long
#define pb emplace_back
int h,w,n,a[maxn][maxn],x,y,l,r,mid,ans=0;
int calc(int x1,int _y1,int x2,int y2){
return a[x2][y2]-a[x1-1][y2]-a[x2][_y1-1]+a[x1-1][_y1-1]; //二维前缀和
}
bool check(int i,int j,int mid){
return (calc(i,j,i+mid-1,j+mid-1)==0); //满足条件即为不含黑色方格
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
read(h); read(w); read(n);
memset(a,0,sizeof(a));
while(n--){
read(x); read(y); a[x][y]=1;
}
for(int i=1;i<=h;++i)
for(int j=2;j<=w;++j) a[i][j]+=a[i][j-1];
for(int i=1;i<=w;++i)
for(int j=2;j<=h;++j) a[j][i]+=a[j-1][i];
//计算二维前缀和数组
for(int i=1;i<=h;++i)
for(int j=1;j<=w;++j){
l=1; r=min(h-i+1,w-j+1); //二分，最小边长是 1，最大边长需要保证不越界
while(l<=r){
mid=(l+r)>>1;
if(check(i,j,mid)) l=mid+1;
else r=mid-1;
}
ans+=r; //二分出 r 为以 (i,j) 为端点的满足条件的正方形最大边长，也是正方形个数
}
writeln(ans);
return 0;
}