题意：
要求存在寻找多少子矩阵，使得子矩阵边界都为1，且内部的0和1的数目相差不超过1。
思路：
直接枚举是
的，要优化到
则需要重复利用一些行的信息，比如可以用前缀和维护连续行连续列的信息（或者二维前缀和维护一个子矩阵）。
本题就是先确定上下界，再枚举其中的列，维护前面i列中0的数目和1的数目，并记录下前缀中每个值的出现次数。
则当连续几行的上界和下界都为1，且当前列都为1，则可以记录下这个前缀，在之前寻找同样的合法前缀，作差后就是一个合法子矩阵了。
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <vector>using namespace std;
typedef unsigned int uint;const int maxn = 1e6 + 7;
const int det = 5e5 + 7;
int a[505][505],sum0[505],sum1[505];
int cnt0[505][505],cnt1[505][505];
int num[maxn];
vector<int>vis;void init() {for(int i = 0;i < vis.size();i++) {num[vis[i]] = 0;}vis.clear();
}int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) {scanf("%d",&a[i][j]);}}int ans = 0;for(int i = 1;i <= n;i++) { //上界for(int j = 1;j <= m;j++) {cnt0[i][j] = (a[i][j] == 0);cnt1[i][j] = (a[i][j] == 1);}for(int j = i + 1;j <= n;j++) { //下界sum0[0] = sum1[0] = 0;for(int k = 1;k <= m;k++) {cnt0[j][k] = cnt0[j - 1][k] + (a[j][k] == 0);cnt1[j][k] = cnt1[j - 1][k] + (a[j][k] == 1);sum0[k] = sum0[k - 1] + cnt0[j][k];sum1[k] = sum1[k - 1] + cnt1[j][k];if(a[j][k] != 1 || a[i][k] != 1) {init();continue;}if(cnt1[j][k] == j - i + 1) {int vinsert = sum1[k] - sum0[k] - k * 2 + det;int vquery = sum1[k - 1] - sum0[k - 1] - (k - 1) * 2 + det;ans += num[vquery] + num[vquery - 1] + num[vquery + 1];num[vinsert]++;vis.push_back(vinsert);}}init();}}printf("%d\n",ans);return 0;
}