#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define pb push_back
#define ff first
#define ss second
const int nax = 2505;
int nx[4] = {0, 0, -1, 1};
int ny[4] = {1, -1, 0, 0};
int n, m;
vector<vi> A;
ll ans = 0ll;
int LG[nax];
int spr[nax][nax][12];
int spc[nax][nax][12];
int vis[nax][nax];
vector<pair<int,int>> comp;
int minix, miniy, maxix, maxiy;
void dfs(int x, int y)
{
vis[x][y] = 1;
comp.pb({x, y});
minix = min(minix, x);
miniy = min(miniy, y);
maxix = max(maxix, x);
maxiy = max(maxiy, y);
for(int i = 0; i < 4; i++)
{
int nwx = nx[i] + x;
int nwy = ny[i] + y;
if(nwx >= 0 && nwx < n && nwy >= 0 && nwy < m)
{
if(vis[nwx][nwy] || A[nwx][nwy])
continue;
dfs(nwx, nwy);
}
}
}
void init()
{
LG[1] = 0;
for(int i = 2; i < nax; i++)
LG[i] = LG[i/2] + 1;
for(int row = 0; row < n; row++)
{
for(int col = 0; col < m; col++)
spr[row][col][0] = spc[col][row][0] = A[row][col];
}
for(int j = 1; j < 12; j++)
{
for(int row = 0; row < n; row++)
{
for(int col = 0; col < m; col++)
{
spr[row][col][j] = max(spr[row][col][j - 1], spr[row][col + (1 << (j - 1))][j - 1]);
spc[col][row][j] = max(spc[col][row][j - 1], spc[col][row + (1 << (j - 1))][j - 1]);
}
}
}
}
int maxir(int row, int l, int r)
{
int j = LG[r - l + 1];
return max(spr[row][l][j], spr[row][r - (1 << j) + 1][j]);
}
int maxic(int col, int l, int r)
{
int j = LG[r - l + 1];
return max(spc[col][l][j], spc[col][r - (1 << j) + 1][j]);
}
ll count_rectangles(vector<vi> a)
{
n = a.size();
m = a[0].size();
A= a;
if(n <= 2 || m <= 2)
return 0ll;
init();
for(int i = 0; i < n; i++)
{
for(int j = 0 ; j < m; j++)
{
if(!vis[i][j] && (A[i][j] == 0))
{
minix = n, maxix = -1;
miniy = m, maxiy = -1;
dfs(i, j);
int sz = comp.size();
if(sz == (maxix- minix + 1) * (maxiy - miniy + 1))
ans++;
comp.clear();
}
}
}
}
