#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct segtree {
vector<ll> tree;
int size;
int n;
int neutral;
void put(int i, ll v) {
tree[i]=v;
}
int combine(ll i, ll j) {
//for min
//return min(i,j);
//for max
return max(i,j);
//for sum
//return i+j;
}
void update(int x, int l, int r, int i) {
if (i>=r || i<l) return;
if (r-l == 1) return;
int mid=(l+r)/2;
update(2*x+1,l,mid,i);
update(2*x+2,mid,r,i);
tree[x]=combine(tree[2*x+1],tree[2*x+2]);
}
void update(int x, int l, int r) {
if (r-l == 1) return;
int mid=(l+r)/2;
update(2*x+1,l,mid);
update(2*x+2,mid,r);
tree[x]=combine(tree[2*x+1],tree[2*x+2]);
}
segtree(vector<int>&a, int neutr) {
n=a.size();
//for min
//neutral = inf;
//for max
//neutral = -inf;
//for sum
//neutral = 0;
neutral = neutr;
size=1;
while (size < n) size*=2;
tree.assign(2*size-1,neutral);
for(int i=0; i<a.size(); ++i) put(size-1+i,a[i]);
update(0,0,size);
}
void clear() {
tree.assign(2*size-1,0);
}
ll calc(int x, int lx, int rx, int l, int r) {
if (lx>=r || rx<=l) return neutral;
if (lx>=l && rx<=r) return tree[x];
int mid=(lx+rx)/2;
int a=calc(2*x+1,lx,mid,l,r),
b=calc(2*x+2,mid,rx,l,r);
return combine(a,b);
}
ll query(int l, int r) {
if (l>=r) return neutral;
return calc(0,0,size,l,r);
}
void set(int i, ll v) {
put(size-1+i,v);
update(0, 0, size, i);
}
void print() {
cout<<"TREE: \n";
int z=0;
while (z<tree.size()) {
for (int i=z; i<2*z+1; i++) cout<<tree[i]<<' ';
cout<<'\n';
z=z*2+1;
}
cout<<'\n';
}
};
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;
//cout<<"component "<<i<<' '<<j<<'\n';
//cout<<minr[a]<<' '<<minc[a]<<' '<<maxr[a]<<' '<<maxc[a]<<' '<<sz[a]<<'\n';
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]);
}
};
DSU dsu(2500,2500);
vector<vector<int>> a;
ll count_rectangles(vector<vector<int>>A) {
a=A;
int n=a.size(), m=a[0].size();
_n=n, _m=m;
if (n<=2 || m<=2) return 0;
if (n==3) {
segtree st(a[1],-1);
ll ans=0;
vector<int> br(m,0);
for (int i=1; i<m-1; ++i) {
br[i] = ( a[1][i]>=a[0][i] || a[1][i]>=a[2][i] );
//cout<<br[i]<<' ';
} //cout<<'\n';
for (int i=1; i<m-1; ++i) {
for (int j=i; j<m-1; ++j) {
if (br[j]) break;
int x=st.query(i,j+1);
ans += (x<a[1][i-1] && x<a[1][j+1]);
}
}
return ans;
}
int mx=0;
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) {
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;
//if (vis[i][j]) continue;
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;
}
if (n<=80 && m<=80) {
vector<vector<vector<int>>> row(n,vector<vector<int>>(m,vector<int>(m,0)));
vector<vector<vector<int>>> col(m,vector<vector<int>>(n,vector<int>(n,0)));
for (int i=1; i<n-1; ++i) {
for (int l=1; l<m-1; ++l) {
for (int r=l; r<m-1; ++r) row[i][l][r]=max(row[i][l][r-1],a[i][r]);
}
}
for (int i=1; i<m-1; ++i) {
for (int l=1; l<n-1; ++l) {
for (int r=l; r<n-1; ++r) col[i][l][r]=max(col[i][l][r-1],a[r][i]);
}
}
int ans=0;
for (int x=1; x<n-1; ++x) {
for (int y=1; y<m-1; ++y) {
for (int i=x; i<n-1; ++i) {
for (int j=y; j<m-1; ++j) {
int foo=1;
for (int k=x; k<=i; ++k) foo&=row[k][y][j]<min(a[k][y-1],a[k][j+1]);
for (int k=y; k<=j; ++k) foo&=col[k][x][i]<min(a[x-1][k],a[i+1][k]);
ans+=foo;
//if (foo) cout<<x<<' '<<y<<' '<<i<<' '<<j<<'\n';
}
}
}
}
return ans;
}
if (n<=200 && m<=200) {
ll ans=0;
vector<vector<vector<int>>> row(n,vector<vector<int>>(m,vector<int>(m,0)));
vector<vector<vector<int>>> col(m,vector<vector<int>>(n,vector<int>(n,0)));
for (int i=1; i<n-1; ++i) {
for (int l=1; l<m-1; ++l) {
for (int r=l; r<m-1; ++r) row[i][l][r]=max(row[i][l][r-1],a[i][r]);
}
for (int l=1; l<m-1; ++l) {
for (int r=l; r<m-1; ++r) row[i][l][r]=row[i][l][r]<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) {
for (int r=l; r<n-1; ++r) col[i][l][r]=max(col[i][l][r-1],a[r][i]);
}
for (int l=1; l<n-1; ++l) {
for (int r=l; r<n-1; ++r) col[i][l][r]=col[i][l][r]<min(a[l-1][i],a[r+1][i]);
}
}
vector<vector<vector<int>>> dp(n,vector<vector<int>>(m,vector<int>(m,0)));
vector<vector<vector<int>>> dp2(n,vector<vector<int>>(m,vector<int>(n,0)));
for (int x=1; x<n-1; ++x) {
for (int y=1; y<m-1; ++y) {
for (int len=1; y+len<m; ++len) {
for (int i=x; i<n-1; ++i) {
if (row[i][y][y+len-1]) dp[x][y][len]++;
else break;
}
}
for (int len=1; x+len<n; ++len) {
for (int j=y; j<m-1; ++j) {
if (col[j][x][x+len-1]) dp2[x][y][len]++;
else break;
}
}
for (int len=1; y+len<m; ++len) {
int k=dp[x][y][len];
for (int l2=1; l2<=k; ++l2) {
int p=dp2[x][y][l2];
if (p>=len) {
ans++;
//cout<<x<<' '<<y<<' '<<len<<' '<<k<<' '<<p<<'\n';
}
}
}
}
}
return ans;
}
return 0;
}
