#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sz(x) (int)x.size()
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
typedef signed i32;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vi32> vvi32;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
long long count_rectangles(vvi a)
{
int n = sz(a); // h
int m = sz(a[0]); // w
vvi fill(n, vi(m, -1));
vvi nextR1(n, vi(m, -1));
vvi nextD1(n, vi(m, -1));
long long res = 0;
rev(m, c)
{
int r1 = n;
rev(n, r)
{
if (a[r][c] == 1)
{
r1 = r;
}
nextD1[r][c] = r1;
}
}
rev(n, r)
{
int c1 = n;
rev(m, c)
{
if (a[r][c] == 1)
{
c1 = c;
}
nextR1[r][c] = c1;
}
}
rev(m, c)
{
int r1 = n;
rev(n, r)
{
if (a[r][c] == 1)
{
r1 = r;
}
nextD1[r][c] = r1;
}
}
vi cnt;
auto dfs = [&](auto &&self, int r, int c, int nr)
{
if (r < 0 || c < 0)
return;
if (r >= n || c >= m)
return;
if (a[r][c] == 1)
return;
fill[r][c] = nr;
cnt[nr]++;
self(self, r - 1, c, nr);
self(self, r + 1, c, nr);
self(self, r, c - 1, nr);
self(self, r, c + 1, nr);
};
int i = 0;
for (int c = 1; c < m - 1; c++)
{
for (int r = 1; r < n - 1; r++)
{
if (a[r][c] == 0 && fill[r][c] == -1)
{
int endr = nextD1[r][c];
int endc = nextR1[r][c];
cnt.pb(0);
dfs(dfs, r, c, i);
if (cnt[i] != (endr - r) * (endc - c))
continue;
bool val = 1;
for (int c2 = c; c2 < endc; c2++)
{
if (!val)
break;
for (int r2 = r; r2 < endr; r2++)
{
if (fill[r2][c2] != i)
{
val = 0;
break;
}
}
}
if (val)
res++;
i++;
}
}
}
return res;
}
