#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(),x.end()
const int maxn = 2550;
const int inf = 1e9+10;
int n, m, a[maxn][maxn];
int lf[maxn][maxn], rg[maxn][maxn], up[maxn][maxn], dw[maxn][maxn];
vector<pair<pair<int,int>,pair<int,int>>> ans;
struct seg1 {
int mn[(1<<13)+10];
vector<int> vec;
void build(vector<int> create) {
vec = create;
upd(1,0,(int) vec.size()-1);
}
void upd(int no, int l, int r) {
if(l == r) {
mn[no] = vec[l];
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
upd(lc,l,mid);
upd(rc,mid+1,r);
mn[no] = min(mn[lc],mn[rc]);
}
int qry(int no, int l, int r, int ll, int rr) {
if(l > rr || r < ll) return inf;
if(l >= ll && r <= rr) return mn[no];
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
return min(qry(lc,l,mid,ll,rr),qry(rc,mid+1,r,ll,rr));
}
}segrg[maxn], segdw[maxn];
struct seg2 {
int mx[(1<<13)+10];
vector<int> vec;
void build(vector<int> create) {
vec = create;
upd(1,0,(int) vec.size()-1);
}
void upd(int no, int l, int r) {
if(l == r) {
mx[no] = vec[l];
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
upd(lc,l,mid);
upd(rc,mid+1,r);
mx[no] = max(mx[lc],mx[rc]);
}
int qry(int no, int l, int r, int ll, int rr) {
if(l > rr || r < ll) return -inf;
if(l >= ll && r <= rr) return mx[no];
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
return max(qry(lc,l,mid,ll,rr),qry(rc,mid+1,r,ll,rr));
}
}seglf[maxn], segup[maxn];
int check(int r1, int r2, int c1, int c2) {
if(c1 > c2 || r1 > r2 || c1 == -1 || c1 == m || c2 == -1 || c2 == m || r1 == -1 || r1 == n || r2 == -1 || r2 == n) return 0;
if(c1 == 0 || c2 == m-1 || r1 == 0 || r2 == n-1) return 0;
int mxlf = -1; mxlf = seglf[c2+1].qry(1,0,n-1,r1,r2);
// for(int i = r1; i <= r2; i++) mxlf = max(mxlf,lf[i][c2+1]);
int mnrg = m; mnrg = segrg[c1-1].qry(1,0,n-1,r1,r2);
// for(int i = r1; i <= r2; i++) mnrg = min(mnrg,rg[i][c1-1]);
int mxup = -1; mxup = segup[r2+1].qry(1,0,m-1,c1,c2);;
// for(int j = c1; j <= c2; j++) mxup = max(mxup,up[r2+1][j]);
int mndw = n; mndw = segdw[r1-1].qry(1,0,m-1,c1,c2);
// for(int j = c1; j <= c2; j++) mndw = min(mndw,dw[r1-1][j]);
if(mxlf < c1 && mnrg > c2 && mxup < r1 && mndw > r2) {
ans.pb(mp(mp(r1,r2),mp(c1,c2)));
return 1;
}
return 0;
}
long long count_rectangles(std::vector<std::vector<int>> A) {
n = A.size();
m = A[0].size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
a[i][j] = A[i][j];
}
}
// primeiro >=
for(int i = 0; i < n; i++) {
stack<pair<int,int>> stk;
// left
for(int j = 0; j < m; j++) {
while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
if(stk.size() == 0) lf[i][j] = -1;
else lf[i][j] = stk.top().sc;
stk.push(mp(a[i][j],j));
}
while(stk.size()) stk.pop();
// right
for(int j = m-1; j >= 0; j--) {
while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
if(stk.size() == 0) rg[i][j] = m;
else rg[i][j] = stk.top().sc;
stk.push(mp(a[i][j],j));
}
}
for(int j = 0; j < m; j++) {
stack<pair<int,int>> stk;
//up
for(int i = 0; i < n; i++) {
while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
if(stk.size() == 0) up[i][j] = -1;
else up[i][j] = stk.top().sc;
stk.push(mp(a[i][j],i));
}
while(stk.size()) stk.pop();
// down
for(int i = n-1; i >= 0; i--) {
while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
if(stk.size() == 0) dw[i][j] = n;
else dw[i][j] = stk.top().sc;
stk.push(mp(a[i][j],i));
}
}
for(int i = 0; i < n; i++) {
vector<int> vec;
for(int j = 0; j < m; j++) {
vec.pb(up[i][j]);
}
segup[i].build(vec);
vec.clear();
for(int j = 0; j < m; j++) {
vec.pb(dw[i][j]);
}
segdw[i].build(vec);
}
for(int j = 0; j < m; j++) {
vector<int> vec;
for(int i = 0; i < n; i++) {
vec.pb(lf[i][j]);
}
seglf[j].build(vec);
vec.clear();
for(int i = 0; i < n; i++) {
vec.pb(rg[i][j]);
}
segrg[j].build(vec);
}
// for(int r1 = 1; r1 < n-1; r1++) {
// for(int r2 = r1; r2 < n-1; r2++) {
// for(int c1 = 1; c1 < m-1; c1++) {
// for(int c2 = c1; c2 < m-1; c2++) {
// if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
// }
// }
// }
// }
for(int r1 = 1; r1 < n-1; r1++) {
for(int c1 = 1; c1 < m-1; c1++) {
int r2,c2;
r2 = dw[r1-1][c1]-1;
c2 = rg[r1][c1-1]-1;
check(r1,r2,c1,c2);
r2 = dw[r1-1][c1]-1;
c2 = rg[r2][c1-1]-1;
check(r1,r2,c1,c2);
}
}
for(int r1 = 1; r1 < n-1; r1++) {
for(int c2 = 1; c2 < m-1; c2++) {
int r2,c1;
r2 = dw[r1-1][c2]-1;
c1 = lf[r1][c2+1]+1;
check(r1,r2,c1,c2);
r2 = dw[r1-1][c2]-1;
c1 = lf[r2][c2+1]+1;
// check(r1,r2,c1,c2);
}
}
for(int r2 = 1; r2 < n-1; r2++) {
for(int c1 = 1; c1 < m-1; c1++) {
int r1,c2;
r1 = up[r2+1][c1]+1;
c2 = rg[r2][c1-1]-1;
check(r1,r2,c1,c2);
}
}
for(int r2 = 1; r2 < n-1; r2++) {
for(int c2 = 1; c2 < m-1; c2++) {
int r1,c1;
r1 = up[r2+1][c2]+1;
c1 = lf[r2][c2+1]+1;
check(r1,r2,c1,c2);
}
}
sort(all(ans));
ans.erase(unique(all(ans)),ans.end());
return ans.size();
}
