#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 2501;
int c[nmax][nmax];// for min
int d[nmax][nmax];// for max
int t[4 * nmax][nmax];
int T[4 * nmax][nmax];
void build(int v, int l, int r, int ind){
if(l == r){
t[v][ind] = c[l][ind];
T[v][ind] = d[l][ind];
return;
}
int m = (l + r) / 2;
build(2 * v, l, m, ind);
build(2 * v + 1, m + 1, r, ind);
t[v][ind] = min(t[v * 2][ind], t[2 * v+ 1][ind]);
T[v][ind] = max(T[v * 2][ind], T[v * 2 + 1][ind]);
}
int get_max(int v, int l, int r, int st, int fin, int ind){
if(l > fin || r < st) return 0;
if(l >= st && r <= fin){
return T[v][ind];
}
int m =(l + r) / 2;
return max(get_max(2 * v, l, m, st, fin, ind),
get_max(2 * v + 1, m + 1, r, st, fin, ind));
}
int get_min(int v, int l, int r, int st, int fin, int ind){
if(l > fin || r < st) return 1e9;
if(l >= st && r <= fin){
return t[v][ind];
}
int m =(l + r) / 2;
return min(get_min(2 * v, l, m, st, fin, ind),
get_min(2 * v + 1, m + 1, r, st, fin, ind));
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size(), m = a[0].size();
for(int i = 0; i < n; i++){
stack <int> st;
for(int j = 0; j < m; j++){
while(!st.empty()){
if(a[i][st.top()] < a[i][j]) st.pop();
else break;
}
if(!st.empty())
d[i][j] = st.top();
st.push(j);
}
while(!st.empty()){
st.pop();
}
for(int j= m - 1 ;j >= 0; j--){
while(!st.empty()){
if(a[i][st.top()] < a[i][j]) st.pop();
else break;
}
if(!st.empty()) c[i][j] = st.top();
else c[i][j] = m - 1;
st.push(j);
}
}
for(int i = 0; i < m; i++){
build(1, 0, n - 1, i);
}
vector <pii> p[m + 1];
for(int j = 0; j < m; j++){
int l[n + 1], r[n + 1];
fill(l , l + n + 1, -1);
fill(r, r + n + 1, n + 1);
stack <int> st;
for(int i = 0; i < n; i++){
while(!st.empty()){
if(a[st.top()][j] > a[i][j]) break;
else st.pop();
}
if(!st.empty()) l[i] = st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n - 1; i >= 0; i--){
while(!st.empty()){
if(a[st.top()][j] > a[i][j]) break;
else st.pop();
}
if(!st.empty()) r[i] = st.top();
st.push(i);
}
for(int i = 0; i < n; i++){
if(l[i] != -1 && r[i] != n + 1)
p[j].pb({l[i] + 1, r[i] - 1});
}
sort(p[j].begin(), p[j].end());
p[j].erase(unique(p[j].begin(), p[j].end()), p[j].end());
}
int ans = 0;
for(int i = 1; i < m - 1; i++){
vector <pii> cur = p[i];
for(int j = i; j < m - 1; j++){
vector <pii> nw;
int inda = 0, indb = 0;
while(inda < cur.size() && indb < p[j].size()){
if(cur[inda] == p[j][indb]) nw.pb(cur[inda]), inda++, indb++;
else{
if(cur[inda] < p[j][indb]) inda++;
else indb++;
}
}
swap(nw, cur);
for(auto to : cur){
int L = to.f, R = to.s;
if(get_max(1, 0, n - 1, L, R, j + 1) >= i) continue;
if(get_min(1, 0, n - 1, L, R, i - 1) <= j) continue;
//cout << i << ' ' << j << ' ' << L << ' ' << R << "\n";
ans++;
}
}
}
return ans;
}
