#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int _n, _m;
struct DSU {
vector<int> p;
vector<int> r;
vector<int> sz, minr, maxr, minc, maxc, vis;
DSU(int N, int M) {
int n=N*M;
p.assign(n,0);
r.assign(n,0);
for (int i=0; i<n; ++i) p[i]=i;
sz.assign(n,1);
minr.assign(n,1);
minc.assign(n,1);
maxr.assign(n,1);
maxc.assign(n,1);
vis.assign(n,0);
for (int i=0; i<n; ++i) {
minr[i]=maxr[i]=i/N;
minc[i]=maxc[i]=i%M;
}
}
int get(int i) {
return p[i]==i ? i : get(p[i]);
}
int calc(int i, int j) {
int a=i*2500+j;
a=get(a);
if (vis[a]) return 0;
vis[a]=1;
if (minr[a]==0 || minc[a]==0 || maxc[a]==_m-1 || maxr[a]==_n-1) return 0;
return sz[a]==(maxr[a]-minr[a]+1)*(maxc[a]-minc[a]+1);
}
void uni(int i, int j, int x, int y) {
int a=i*2500+j, b=x*2500+y;
a=get(a);
b=get(b);
if (a==b) return;
if (r[a]==r[b]) r[a]++;
if (r[a]<r[b]) {
swap(a,b);
}
p[b]=a;
sz[a]+=sz[b];
minr[a]=min(minr[a],minr[b]);
maxr[a]=max(maxr[a],maxr[b]);
minc[a]=min(minc[a],minc[b]);
maxc[a]=max(maxc[a],maxc[b]);
}
};
ll count_rectangles(vector<vector<int>>a) {
int n=a.size(), m=a[0].size();
_n=n, _m=m;
int mx=0;
if (n<=2 || m<=2) return 0;
if (n==3) {
ll ans=0;
int left=0;
for (int i=1; i<m-1; ++i) {
mx=0;
for (int j=i; j<m-1; ++j) {
mx=max(mx,a[1][j]);
if (a[1][j]>=min(a[0][j],a[2][j])) break;
if (mx<min(a[1][i-1],a[1][j+1])) ++ans;
}
}
return ans;
}
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) mx=max(mx,a[i][j]);
}
if (mx==0) return 0;
if (mx==1) {
DSU dsu(2500,2500);
vector<vector<int>> vis(n,vector<int>(m,0));
queue<pair<int,int>> q;
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
if (a[i][j]==0) q.push({i,j});
}
}
while (!q.empty()) {
auto u=q.front(); q.pop();
int i=u.first, j=u.second;
vis[i][j]=1;
if (i && a[i-1][j]==0) {
dsu.uni(i,j,i-1,j);
vis[i-1][j]=1;
}
if (i<n-1 && a[i+1][j]==0) {
dsu.uni(i,j,i+1,j);
vis[i+1][j]=1;
}
if (j && a[i][j-1]==0) {
dsu.uni(i,j,i,j-1);
vis[i][j-1]=1;
}
if (j<m-1 && a[i][j+1]==0) {
dsu.uni(i,j,i,j+1);
vis[i][j+1]=1;
}
}
ll ans=0;
for (int i=1; i<n-1; ++i) {
for (int j=1; j<m-1; ++j) {
if (a[i][j]==0) ans+=dsu.calc(i,j);
}
}
return ans;
}
ll ans=0;
vector<vector<bitset<700>>> row(n,vector<bitset<700>>(m));
vector<vector<bitset<700>>> col(m,vector<bitset<700>>(n));
vector<int> dp(n,0);
for (int i=1; i<n-1; ++i) {
for (int l=1; l<m-1; ++l) {
mx=0;
for (int r=l; r<m-1; ++r) {mx=max(mx,a[i][r]); row[i][l][r]=mx<min(a[i][l-1],a[i][r+1]); }
}
}
for (int i=1; i<m-1; ++i) {
for (int l=1; l<n-1; ++l) {
mx=0;
for (int r=l; r<n-1; ++r) {mx=max(mx,a[r][i]); col[i][l][r]=mx<min(a[l-1][i],a[r+1][i]); }
}
}
for (int x=1; x<n-1; ++x) {
for (int y=1; y<m-1; ++y) {
dp.assign(n,0);
for (int len=1; x+len<n; ++len) {
for (int j=y; j<m-1; ++j) {
if (col[j][x][x+len-1]) dp[len]++;
else break;
}
}
for (int len=1; y+len<m; ++len) {
for (int i=x; i<n-1; ++i) {
if (row[i][y][y+len-1]) { if (dp[i-x+1]>=len) ++ans; }
else break;
}
}
}
}
return ans;
}
