题意简述： 求一个01矩形中满足“左上角一正方形区域全为1，其余全为0”的子矩形数。

思路：先枚举出合法的正方形，再从每个正方形扩展合法的矩形。时间复杂度$O(n^2\log{n})$。只T了一个点，其它点最慢$363ms$，请问是否有卡掉我这个做法的$hack$数据？或者还可以如何优化？谢谢qwq

#include<bits/stdc++.h>
#define ll long long
#define gch getchar()
#define _ putchar(' ')
#define __ puts("")
#define st first
#define nd second
using namespace std;
ll rd()
{
	ll f=1,x=0; char c;
	while(!isdigit(c=gch)) if(c==45)f=-1;
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=gch;
	return f*x;
}
void wt(ll x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) wt(x/10);
	putchar(x%10+'0');
}
const int N=2005,M=4e6+5;
int n,m,ct1,ct2,sm[N][N];
pair<int,int>t[M]; ll as;
struct square{int x,y,len;}s[M];
bool ck1(int a,int b,int l){return sm[a+l][b+l]-sm[a-1][b+l]-sm[a+l][b-1]+sm[a-1][b-1]==(l+1)*(l+1);}
bool ck2(int a,int b,int c,int d,int ss){return sm[a][b]-sm[a][d-1]-sm[c-1][b]+sm[c-1][d-1]==ss;}
int main()
{
	n=rd(),m=rd();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) 
		{
			int a=rd(); if(a) t[++ct1]={i,j};
			sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+a;
		}
	for(int k=1;k<=ct1;k++)
	{
		int i=t[k].st,j=t[k].nd,l=0,r=min(n-i,m-j),mid;
		while(l<r){if(ck1(i,j,mid=l+r>>1))l=mid+1;else r=mid;}
		if(ck1(i,j,l-1)) s[++ct2]={i,j,l-1};
	}
	for(int k=1;k<=ct2;k++)
	{
		int kx=s[k].x,ky=s[k].y,kl=s[k].len,ks=(kl+1)*(kl+1);
		for(int i=kl+1;i<=n-kx;i++)
		{
			int a=kx+i,l=kl+1,r=m-ky+1,mid;
			while(l<r){mid=(l+r)>>1;if(ck2(a,ky+mid,kx,ky,ks))l=mid+1;else r=mid;}
			if(ck2(a,ky+l-1,kx,ky,ks)) as+=l-1-kl; else break;
		}
	}
	wt(as);
	return 0;
}