题解
subtask3,4
枚举四边界再暴搜找连通块，时间复杂度 O( n6 )
subtask5,6
发现只有子矩阵内只有一个黑色格子才合法，所以枚举上下右边界，
左边界范围考虑维护两个指针维护，时间复杂度 O( n3 )
subtask7,8
不妨把每个黑点当成点，相邻黑点间有条边，考虑欧拉公式 n + r = m + 2，即点数 + 面数 = 边数 + 2，
由于不存在空腔所以 r( 面数 ) = 四元环( 四点四边的环 ) 个数 + 1，因此有 n + 四元环个数 - m = 1 把 点，横边，竖边，四元环找出来前缀和，
枚举上下右边界，左边界用桶直接求 时间复杂度 O( n3 )
subtask9,10
发现如果一个子矩形里面存在空腔，则将其四边界扩展后空腔仍存在 bfs找出所有空腔，总数上限为 n2，在固定了上下右边界后，
每个空腔是对左边界的限制 把空腔所在的子矩形(x1,y1,x2,y2)找出来，在上边界<=x1-1时在 (x2+1,y2+1) 处打上y1-1的限制，
之后枚举下右边界时再处理出c[i]表示当前右边界为i的最大左边界，指针+桶单调维护左边界 时间复杂度 O( n3 )
备注：设前缀和为 f [ i ] - f [ j ]，要求 f [ i ] - f [ j ] = 1，即 f [ i ] - 1 = f [ j ]，用桶维护 j 的个数，枚举 i 求和。
#include<cstdio> #include<algorithm> #define ll long long using namespace std; const int N=305,M=N*N; struct zy{int x,y,u;}c[N*N]; struct yz{int f,f1,g,g1,h,h1,l,l1;}f[N]; int w[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; int a[N][N],bz[N][N],b[N][N],p[N],q[N],s[N*N*2]; int n,m,i,j,l,r,u,d,t,cl,an,l1,l2; char ch[N]; inline int max(int x,int y){return x>y ? x:y;} inline int min(int x,int y){return x<y ? x:y;} inline int cmp(zy x,zy y){return x.u<y.u;} inline int pd(int x,int y){return a[x][y]+a[x-1][y]+a[x][y-1]+a[x-1][y-1]==4;} inline int fj(int x){return f[x].f+f[x-1].g+f[x].h+f[x-1].l;} inline int fi(int x){return f[x].f+f[x].g+f[x].h+f[x].l;} void dfs(int x,int y){ int xx,yy,o; bz[x][y]=1; l=min(l,y); r=max(r,y); u=min(u,x); d=max(d,x); for(o=0;o<=3;++o){ xx=x+w[o][0]; yy=y+w[o][1]; if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]==0&&bz[xx][yy]==0) dfs(xx,yy); } } int main(){ freopen("village.in","r",stdin); freopen("village.out","w",stdout); scanf("%d%d ",&n,&m); for(i=1;i<=n;++i){ scanf("%s ",ch+1); for(j=1;j<=m;++j) a[i][j]=ch[j]-'0'; } for(i=n;i>=1;--i) for(j=m;j>=1;--j) if (a[i][j]==0&&bz[i][j]==0){ l=u=N; r=d=0; dfs(i,j); if (l==1||r==m||u==1||d==n||b[d+1][r+1]) continue; b[d+1][r+1]=l-1; c[++t].u=u; c[t].x=d+1; c[t].y=r+1; } sort(c+1,c+t+1,cmp); cl=1; for(i=1;i<=n;++i){ while(cl<=t&&i>=c[cl].u) b[c[cl].x][c[cl].y]=0,cl++; for(j=1;j<=m;++j){ p[j]=0; f[j].f1=0; f[j].g1=a[i][j]; f[j].l1=0; f[j].h1=-(a[i][j-1]+a[i][j]==2); } for(d=i;d<=n;++d){ l=r=m; for(j=1;j<=m;++j){ p[j]=max(p[j],b[d][j]); q[j]=max(q[j-1],p[j]); f[j].f=f[j-1].f+f[j].f1; f[j].g=f[j-1].g+f[j].g1; f[j].l=f[j-1].l+f[j].l1; f[j].h=f[j-1].h+f[j].h1; } for(j=m;j>=1;--j){ while(l>q[j]) s[fj(l)+M]++,l--; while(r>l&&r>j) s[fj(r)+M]--,r--; an+=s[fi(j)+M-1]; } while(r>l) s[fj(r)+M]--,r--; if (d<n) for(j=1;j<=m;++j){ f[j].f1+=pd(d+1,j); f[j].g1+=a[d+1][j]; f[j].l1-=a[d][j]+a[d+1][j]==2; f[j].h1-=a[d+1][j-1]+a[d+1][j]==2; } } } printf("%d",an); return 0; }