#include "rect.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <stack>
#include <queue>
typedef long long llong;
const int MAXN = 2500 + 10;
const int INF = 1e9;
int n, m;
struct BIT
{
int tree[MAXN], max;
inline void reset(const int &_max)
{
max = _max;
std::fill(tree + 1, tree + 1 + max, 0);
}
inline void update(const int &pos, const int &value)
{
for (int idx = pos ; idx <= max ; idx += idx & (-idx))
{
tree[idx] += value;
}
}
inline int query(const int &pos)
{
int res = 0;
for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
};
BIT fenwick;
int a[MAXN][MAXN];
int p[MAXN][MAXN];
int up[MAXN][MAXN];
int left[MAXN][MAXN];
int down[MAXN][MAXN];
int right[MAXN][MAXN];
std::stack <int> st[MAXN];
std::queue <int> q[MAXN];
int minRight[MAXN];
int maxLeft[MAXN];
bool isIN[MAXN];
void clearStacks()
{
for (int i = 1 ; i <= std::max(n, m) ; ++i)
{
while (!st[i].empty())
{
st[i].pop();
}
}
}
inline int getSum(int r1, int c1, int r2, int c2)
{
--r1; --c1;
return p[r2][c2] - p[r1][c2] - p[r2][c1] + p[r1][c1];
}
inline int getSum2(int r1, int c1, int r2, int c2)
{
--r1; --c1;
return (r2 - r1) * (c2 - c1) - (p[r2][c2] - p[r1][c2] - p[r2][c1] + p[r1][c1]);
}
llong count_rectangles(std::vector <std::vector <int>> A)
{
bool zeroOne = true;
n = A.size(); m = A[0].size();
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j <= m ; ++j)
{
a[i][j] = A[i - 1][j - 1];
p[i][j] = a[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
zeroOne &= (a[i][j] < 2);
}
}
for (int i = 0 ; i <= m + 1 ; ++i)
{
a[0][i] = a[n + 1][i] = INF;
}
for (int i = 0 ; i <= n + 1 ; ++i)
{
a[i][0] = a[i][m + 1] = INF;
}
if (n <= 2 || m <= 2)
{
return 0;
}
// up
for (int i = 1 ; i <= m ; ++i)
{
st[i].push(0);
}
for (int row = 1 ; row <= n ; ++row)
{
for (int col = 1 ; col <= m ; ++col)
{
while (!st[col].empty() && a[st[col].top()][col] < a[row][col])
{
st[col].pop();
}
up[row][col] = st[col].top();
st[col].push(row);
}
}
// down
clearStacks();
for (int i = 1 ; i <= m ; ++i)
{
st[i].push(n + 1);
}
for (int row = n ; row >= 1 ; --row)
{
for (int col = 1 ; col <= m ; ++col)
{
while (!st[col].empty() && (a[st[col].top()][col] < a[row][col] || (zeroOne && a[st[col].top()][col] == a[row][col])))
{
st[col].pop();
}
down[row][col] = st[col].top();
st[col].push(row);
}
}
// left
clearStacks();
for (int i = 1 ; i <= n ; ++i)
{
st[i].push(0);
}
for (int row = 1 ; row <= n ; ++row)
{
for (int col = 1 ; col <= m ; ++col)
{
while (!st[row].empty() && a[row][st[row].top()] < a[row][col])
{
st[row].pop();
}
left[row][col] = st[row].top();
st[row].push(col);
}
}
// right
clearStacks();
for (int i = 1 ; i <= n ; ++i)
{
st[i].push(m + 1);
}
for (int row = 1 ; row <= n ; ++row)
{
for (int col = m ; col >= 1 ; --col)
{
while (!st[row].empty() && (a[row][st[row].top()] < a[row][col] || (zeroOne && a[row][st[row].top()] == a[row][col])))
{
st[row].pop();
}
right[row][col] = st[row].top();
st[row].push(col);
}
}
llong ans = 0;
if (zeroOne)
{
for (int r1 = 2 ; r1 <= n ; ++r1)
{
for (int c1 = 2 ; c1 <= m ; ++c1)
{
if (a[r1 - 1][c1] == 0 || a[r1][c1 - 1] == 0 || a[r1][c1] == 1)
{
continue;
}
int c2 = right[r1][c1] - 1;
if (c2 < m)
{
int r2 = down[r1][c2] - 1;
if (r2 < n && getSum(r1, c1, r2, c2) == 0 && getSum2(r1 - 1, c1, r1 - 1, c2) == 0 && getSum2(r1, c1 - 1, r2, c1 - 1) == 0 && getSum2(r2 + 1, c1, r2 + 1, c2) == 0 && getSum2(r1, c2 + 1, r2, c2 + 1) == 0)
{
ans++;
}
}
}
}
return ans;
}
for (int row1 = 1 ; row1 + 2 <= n ; ++row1)
{
for (int col = 1 ; col <= m ; ++col)
{
maxLeft[col] = 0;
minRight[col] = INF;
}
for (int row2 = row1 + 2 ; row2 <= n ; ++row2)
{
for (int col = 1 ; col <= m ; ++col)
{
maxLeft[col] = std::max(maxLeft[col], left[row2 - 1][col]);
minRight[col] = std::min(minRight[col], right[row2 - 1][col]);
while (!q[col].empty()) q[col].pop();
isIN[col] = false;
}
fenwick.reset(m);
int need = m;
int ptr = m;
for (int col = m ; col >= 1 ; --col)
{
if (col != m)
{
if (down[row1][col + 1] < row2 || up[row2][col + 1] > row1)
{
need = col + 1;
}
}
while (!q[col].empty())
{
int top = q[col].front();
if (isIN[top]) fenwick.update(top, -1);
isIN[top] = false;
q[col].pop();
}
while (ptr > need)
{
if (isIN[ptr])
{
fenwick.update(ptr, -1);
isIN[ptr] = false;
}
ptr--;
}
int to = std::min(need, minRight[col]);
if (col + 1 != to)
{
ans += fenwick.query(to) - isIN[col + 1];
}
isIN[col] = true;
fenwick.update(col, 1);
if (maxLeft[col]) q[maxLeft[col] - 1].push(col);
}
}
}
return ans;
}
