#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
ll n, m;
ll pow2N, pow2M;
vector<vector<ll>> segN, segM;
unordered_map<ll, ll> sN, sM;
ll segMaxN(ll low, ll high, ll m) {
ll hash = (low << 32) | (high << 16) | m;
if (sN[hash]) return sN[hash];
low += pow2N; high += pow2N;
ll mx = 0;
while (low <= high) {
if (low & 1) mx = max(mx, segN[m][low++]);
if (!(high & 1)) mx = max(mx, segN[m][high--]);
low /= 2; high /= 2;
}
return sN[hash] = mx;
}
ll segMaxM(ll low, ll high, ll n) {
ll hash = (low << 32) | (high << 16) | n;
if (sM[hash]) return sM[hash];
low += pow2M; high += pow2M;
ll mx = 0;
while (low <= high) {
if (low & 1) mx = max(mx, segM[n][low++]);
if (!(high & 1)) mx = max(mx, segM[n][high--]);
low /= 2; high /= 2;
}
return sM[hash] = mx;
}
ll count_rectangles(vector<vector<int>> a) {
if (a.size() <= 2) return 0;
n = a.size(); m = a[0].size();
if (n > 200 && m > 200) {
if (a.size() <= 2) return 0;
n = a.size(); m = a[0].size();
vector<vector<bool>> vst(n, vector<bool>(m));
ll res = 0;
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) {
if (a[i][j] || vst[i][j]) continue;
ll ptrN = i, ptrM = j;
while (!a[ptrN][ptrM] && ptrM < m-1) ptrM++;
ptrM--;
while (!a[ptrN][ptrM] && ptrN < n-1) ptrN++;
ptrN--;
bool poss = true;
for (int x = i; x <= ptrN && poss; x++) {
for (int y = j; y <= ptrM && poss; y++) {
vst[x][y] = true;
if (a[x][y]) poss = false;
}
}
for (int x = i; x <= ptrN && poss; x++) {
if (!a[x][j-1]) poss = false;
if (!a[x][ptrM+1]) poss = false;
}
for (int y = j; y <= ptrM && poss; y++) {
if (!a[i-1][y]) poss = false;
if (!a[ptrN+1][y]) poss = false;
}
res += poss;
}
}
return res;
}
pow2N = 1ll << (ll)ceil(log2(n));
pow2M = 1ll << (ll)ceil(log2(m));
sN = unordered_map<ll, ll>(); sM = unordered_map<ll, ll>();
vector<int> am = a[1];
segN = vector<vector<ll>>(m, vector<ll>(2*pow2N));
segM = vector<vector<ll>>(n, vector<ll>(2*pow2M));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
segN[j][pow2N+i] = a[i][j];
segM[i][pow2M+j] = a[i][j];
}
}
for (int meta = 0; meta < n; meta++) {
for (int i = pow2M-1; i > 0; i--) {
segM[meta][i] = max(segM[meta][2*i], segM[meta][2*i+1]);
}
}
for (int meta = 0; meta < m; meta++) {
for (int i = pow2N-1; i > 0; i--) {
segN[meta][i] = max(segN[meta][2*i], segN[meta][2*i+1]);
}
}
unordered_set<ll> s;
ll res = 0;
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) {
ll left = j, right = j, top = i, bottom = i;
ll ref = a[i][j];
ll low = 0, high = j;
while (low < high) {
ll mid = (low + high + 1) / 2;
if (segMaxM(mid, high, i) <= ref) {
high = mid-1;
}
else {
low = mid;
}
}
left = low+1;
low = j, high = m-1;
while (low < high) {
ll mid = (low + high) / 2;
if (segMaxM(low, mid, i) <= ref) {
low = mid+1;
}
else {
high = mid;
}
}
right = high-1;
low = 0, high = i;
while (low < high) {
ll mid = (low + high + 1) / 2;
if (segMaxN(mid, high, j) <= ref) {
high = mid-1;
}
else {
low = mid;
}
}
top = low+1;
low = i, high = n-1;
while (low < high) {
ll mid = (low + high) / 2;
if (segMaxN(low, mid, j) <= ref) {
low = mid+1;
}
else {
high = mid;
}
}
bottom = high-1;
ll hash = (left << 48) | (right << 32) | (top << 16) | bottom;
if (s.count(hash)) continue;
s.insert(hash);
ll lN = bottom-top+1, lM = right-left+1;
bool poss = 1;
for (int meta = top; meta < top+lN && poss; meta++) {
ll border = min(a[meta][left-1], a[meta][left+lM]);
if (border <= segMaxM(left, left+lM-1, meta)) {
poss = 0;
}
}
for (int meta = left; meta < left+lM && poss; meta++) {
ll border = min(a[top-1][meta], a[top+lN][meta]);
if (border <= segMaxN(top, top+lN-1, meta)) {
poss = 0;
}
}
res += poss;
}
}
return res;
}
