#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
const int MAXN = 3510, MAXK = 13;
int n, m;
int colMax[MAXN][MAXN][MAXK];
int rowMax[MAXN][MAXN][MAXK];
int lg[MAXN];
void buildST() {
FOR(i, 2, MAXN-1) lg[i] = lg[i/2]+1;
FOR(j, 1, MAXK-1) FOR(k, 0, m-1) for (int i = 0; i + (1<<j) <= n; i++) {
colMax[k][i][j] = max(colMax[k][i][j-1], colMax[k][i + (1<<(j-1))][j-1]);
}
FOR(j, 1, MAXK-1) FOR(k, 0, n-1) for (int i = 0; i + (1<<j) <= m; i++) {
rowMax[k][i][j] = max(rowMax[k][i][j-1], rowMax[k][i + (1<<(j-1))][j-1]);
}
}
int getColMax (int k, int fr, int to) {
int j = lg[to-fr+1];
return max(colMax[k][fr][j], colMax[k][to - (1<<j)+ 1][j]);
}
int getRowMax (int k, int fr, int to) {
int j = lg[to-fr+1];
return max(rowMax[k][fr][j], rowMax[k][to - (1<<j)+ 1][j]);
}
int par[MAXN*MAXN], sz[MAXN*MAXN], mnR[MAXN*MAXN], mxR[MAXN*MAXN], mnC[MAXN*MAXN], mxC[MAXN*MAXN];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
void unite (int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
par[b] = a;
sz[a] += sz[b];
mnR[a] = min(mnR[a], mnR[b]);
mnC[a] = min(mnC[a], mnC[b]);
mxR[a] = max(mxR[a], mxR[b]);
mxC[a] = max(mxC[a], mxC[b]);
}
int getId (int i, int j) {
return i*m + j;
}
long long sub6(std::vector<std::vector<int> > a) {
FOR(i, 0, n-1) FOR(j, 0, m-1) {
int id = getId(i,j);
par[id] = id;
sz[id] = 1;
mnR[id] = mxR[id] = i;
mnC[id] = mxC[id] = j;
}
FOR(i, 0, n-1) FOR(j, 0, m-1) {
if(a[i][j] == 1) continue;
if (i < n-1 && a[i+1][j] == 0)
unite(getId(i,j), getId(i+1,j));
if (j < m-1 && a[i][j+1] == 0)
unite(getId(i,j), getId(i, j+1));
}
ll ans = 0ll;
FOR(i, 0, n-1) FOR(j, 0, m-1) {
if (a[i][j] == 1) continue;
int id = getId(i,j);
if (find(id) != id) continue;
if (mxR[id] == n-1 || mxC[id] == m-1 || mnR[id] == 0 || mnC[id] == 0) continue;
if (sz[id] == (mxR[id] - mnR[id] + 1) * (mxC[id] - mnC[id] + 1))
ans++;
}
return ans;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = (int)a.size();
m = (int)a[0].size();
bool s6 = true;
FOR(i, 0 ,n-1) FOR(j, 0, m-1) if (a[i][j] > 1) s6 = false;
if (s6) {
return sub6(a);
}
FOR(i, 0, n-1) FOR(j, 0, m-1) colMax[j][i][0] = rowMax[i][j][0] = a[i][j];
buildST();
/*FOR(r1, 0, n-1) FOR(c1, 0, m-1) FOR(r2, r1, n-1) {
cout << " colMax, col: " << c1 << " ["<<r1<<", "<<r2<<"] mx= " << getColMax(c1, r1, r2) << endl;
}
FOR(r1, 0, n-1) FOR(c1, 0, m-1) FOR(c2, c1, m-1) {
cout << " rowMax, row: " << r1 << " ["<<c1<<", "<<c2<<"] mx= " << getRowMax(r1, c1, c2) << endl;
}*/
ll ans = 0ll;
FOR(r1, 1, n-2) FOR(c1, 1, m-2) FOR(r2, r1, n-2) FOR(c2, c1, m-2) {
bool ok = true;
/*FOR(i, r1, r2) FOR(j, c1, c2) {
int mnH = a[i][c1-1];
mnH = min(mnH, a[i][c2+1]);
mnH = min(mnH, a[r1-1][j]);
mnH = min(mnH, a[r2+1][j]);
if(a[i][j] >= mnH) {
ok = false;
break;
}
}*/
FOR(i, r1, r2) {
int mnH = min(a[i][c1-1], a[i][c2+1]);
int mxH = getRowMax(i, c1, c2);
if (mxH >= mnH) {
ok = false;
break;
}
}
if (ok) {
FOR(j, c1, c2) {
int mnH = min(a[r1-1][j], a[r2+1][j]);
int mxH = getColMax(j, r1, r2);
if(mxH >= mnH) {
ok = false;
break;
}
}
}
if (ok) ans++;
}
return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
ans:
6
4 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
*/
