#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define fi first
#define se second
#define rep(a,b,c) for(int a=b; a<c; a++)
#define pb push_back
using namespace std;
const int moves[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
ll count_rectangles(vector<vector<int>> a) {
ll ans=0, n=a.size(), m=a[0].size();
if(max(n,m)>200){
queue<int> q;
int x, y, z, b[4];
rep(i,0,n){
rep(j,0,m){
if(a[i][j]) continue;
q.push(i);
q.push(j);
z=0;
while(q.size()){
x=q.front();q.pop();
y=q.front();q.pop();
a[x][y]=1;
if(!x || !y || x+1==n || y+1==m) z=-1e9;
b[1]=max(b[1],x);
b[0]=min(b[0],x);
b[3]=max(b[3],y);
b[2]=min(b[2],y);
z++;
rep(k,0,4){
x+=moves[k][0];
y+=moves[k][1];
if(0<=x && x<n && 0<=y && y<m && !a[i][j]){
q.push(x);
q.push(y);
}
x-=moves[k][0];
y-=moves[k][1];
}
}
if((b[1]-b[0]+1)*(b[3]-b[2]+1)==z) ans+=z;
}
}
}
rep(ri,1,n-1){
rep(ci,1,m-1){
rep(rf,ri,n-1){
rep(cf,ci,m-1){
bool rect=1;
rep(i,ri,rf+1){
rep(j,ci,cf+1){
if(a[i][j]>=a[ri-1][j] || a[i][j]>=a[rf+1][j] || a[i][j]>=a[i][ci-1] || a[i][j]>=a[i][cf+1]){
rect=false;
break;
}
}
if(!rect) break;
}
ans+=rect;
}
}
}
}
return ans;
}
