并没有用标签的做法，属于乱搞做法，复杂度比较依赖数据。
Solution
- (O(n^5)) 做法：
枚举 (x_1,y_1,x_2,y_2)，然后 (O(n))判断是否合法。
- (O(n^4)) 做法：
可以维护一个前缀和 (O(1)) 判断两个点之间是否都是 (0)。
- (O(n^3)) 做法：
预处理一个 (up_{i,j}) 和 (down_{i,j}) 分别表示这个点向上和向下最多延伸的距离。取 (min) 就可以得到该点的最大延伸距离 (h_{i,j})。
考虑枚举每一条长度为 (0) 的横线 ([l,r])，假设这条横线在第 (i) 行，那么这条横线的贡献就是两个端点的最大延伸距离的较小值。即 (min(h_{i,l},h_{i,r}))。
枚举行数加上枚举每条横线的两个端点，总复杂度 (O(n^3))。
- (O(n^2) sim O(n^3)) 的做法
发现每次枚举到一条横线只是计算了它两端点的贡献，考虑把横线上两点之间的贡献一起算。
如果固定一个点 (x)，考虑它对横线上其他点 (y) 的贡献。那么当且仅当 (h_{i,x} le h_{i,y}) 时，这两个点形成的 “H” 的贡献为 (h_{i,x})。
不过这样做当 (h_{i,x} = h_{i,y}) 时 (h_{i,x}) 的贡献会被计算两次，把这部分单独拿出来特判掉即可。
如何快速的找到 (ge h_{i,x}) 的值的数量？
我这里使用的是桶排，把每个 (h_{i,x}) 放进桶里，从后向前做前缀和，(h_{i,x}) 位置对应的前缀和 (-1) 就是 (ge h_{i,x}) 的值的数量。
这里我先找到了这段横线中最大的 (h_{i,x})，可以在预处理前缀和的时候减少枚举量。
这个做法在随机数据下跑的很快，感谢出题人没有把我卡成 (O(n^3))。
- (O(n^2 log n)) 的做法
如果把上面的横线放进树状数组维护，复杂度是稳定的 (log) 。
Code
代码写的是倒数第二个做法。
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
int n, m, Ans = 0;
bool a[2020][2020];
int sumh[2020][2020];
int up[2020][2020], down[2020][2020];
int cnt[2020];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
signed main()
{
n = read(), m = read();
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
a[i][j] = read();
sumh[i][j] = sumh[i][j - 1] + a[i][j];
if(a[i][j]) {
up[i][j] = i;
} else {
up[i][j] = up[i - 1][j];
}
}
}
for(int i = 1; i <= m; ++i) {
down[n + 1][i] = n + 1;
}
for(int i = n; i >= 1; --i) {
for(int j = m; j >= 1; --j) {
if(a[i][j]) {
down[i][j] = i;
} else {
down[i][j] = down[i + 1][j];
}
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
up[i][j] = min(i - up[i][j] - 1, down[i][j] - i - 1);
}
}
for(int i = 1; i <= n; ++i) {
a[i][m+1] = 1;
for(int j = 1, l = 1, r = 0; j <= m + 1; ++j) {
if(a[i][j]) {
if(l < r) {
int Sum = 0, Sum2 = 0;
memset(cnt, false, sizeof cnt);
int Max = -1;
for(int g = l; g <= r; ++g) cnt[up[i][g]] ++, Max = max(Max, up[i][g]);
for(int g = Max; g >= 0; --g) cnt[g] += cnt[g + 1];
for(int g = l; g <= r; ++g) Sum2 += up[i][g] * (cnt[up[i][g]] - cnt[up[i][g]+1] - 1), Sum += up[i][g] * cnt[up[i][g] + 1];
Ans += Sum + Sum2 / 2;
}
l = r = j + 1;
} else {
r = j;
}
}
}
printf("%lld", Ans);
return 0;
}