#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
typedef pair<short, short> pii;
#define fi first
#define se second
#define mp make_pair
const short N = 2505;
struct segtree{
vector<short> ele;
short mode;
short n;
void init(short sz, short md){
mode = md;
n = sz;
if(md == 0)
ele.resize(2 * n, 5000);
else
ele.resize(2 * n, -1);
}
void upd(short id, short v){
id += n;
if(mode == 0)
ele[id] = min(ele[id], v);
else
ele[id] = max(ele[id], v);
id >>= 1;
while(id > 0){
if(mode == 0) ele[id] = min(ele[id << 1], ele[id << 1 | 1]);
else ele[id] = max(ele[id << 1], ele[id << 1 | 1]);
id >>= 1;
}
}
short get(short l, short r){
l += n;
r += n;
short res = -1;
if(mode == 0) res = 5000;
while(l <= r){
if((l & 1)){
if(mode == 0) res = min(res, ele[l]);
else res = max(res, ele[l]);
l ++ ;
}
if(!(r & 1)){
if(mode == 0) res = min(res, ele[r]);
else res = max(res, ele[r]);
r -- ;
}
l >>= 1;
r >>= 1;
}
return res;
}
};
segtree L[N], R[N], U[N], D[N];
short Lf[N][N], Rf[N][N], Uf[N][N], Df[N][N];
bool is_valid(short i1, short j1, short i2, short j2){
if(i1 == -1 || j1 == -1 || i2 == -1 || j2 == -1) return false;
if(R[j1].get(i1 + 1, i2 - 1) < j2) return false;
if(L[j2].get(i1 + 1, i2 - 1) > j1) return false;
if(D[i1].get(j1 + 1, j2 - 1) < i2) return false;
if(U[i2].get(j1 + 1, j2 - 1) > i1) return false;
return true;
}
ll count_rectangles(vector<vector<int>> e){
int n = e.size();
int m = e[0].size();
vector<int> mono;
for(int i = 0 ; i < m ; i ++ ){
L[i].init(n,1);
R[i].init(n,0);
}
for(int i = 0 ; i < n; i ++ ){
mono.clear();
for(int j = 0 ; j < m ; j ++ ){
Lf[i][j] = -1;
while(!mono.empty() && e[i][mono.back()] <= e[i][j]){
if(e[i][mono.back()] == e[i][j]){
L[j].upd(i, mono.back());
}
mono.pop_back();
}
if(!mono.empty()){
Lf[i][j] = mono.back();
L[j].upd(i, mono.back());
}
mono.push_back(j);
}
mono.clear();
for(int j = m - 1; j >= 0 ; j -- ){
Rf[i][j] = -1;
while(!mono.empty() && e[i][mono.back()] <= e[i][j]){
if(e[i][mono.back()] == e[i][j]){
R[j].upd(i, mono.back());
}
mono.pop_back();
}
if(!mono.empty()){
Rf[i][j] = mono.back();
R[j].upd(i, mono.back());
}
mono.push_back(j);
}
}
for(int i = 0 ; i < n; i ++ ){
U[i].init(m, 1);
D[i].init(m, 0);
}
for(int j = 0 ; j < m ; j ++ ){
mono.clear();
for(int i = 0 ; i < n; i ++ ){
Uf[i][j] = -1;
while(!mono.empty() && e[mono.back()][j] <= e[i][j]){
if(e[mono.back()][j] == e[i][j]){
U[i].upd(j, mono.back());
}
mono.pop_back();
}
if(!mono.empty()){
Uf[i][j] = mono.back();
U[i].upd(j, mono.back());
}
mono.push_back(i);
}
mono.clear();
for(int i = n - 1; i >= 0 ; i -- ){
Df[i][j] = -1;
while(!mono.empty() && e[mono.back()][j] <= e[i][j]){
if(e[mono.back()][j] == e[i][j]){
D[i].upd(j, mono.back());
}
mono.pop_back();
}
if(!mono.empty()){
Df[i][j] = mono.back();
D[i].upd(j, mono.back());
}
mono.push_back(i);
}
}
vector<pair<pii, pii>> rect;
for(int i = 1; i + 1 < n; i ++ ){
for(int j = 1; j + 1 < m ; j ++ ){
if(is_valid(Uf[i][j], Lf[i][j], Df[i][j], Rf[i][j]))
rect.push_back({mp(Uf[i][j], Lf[i][j]), mp(Df[i][j], Rf[i][j])});
}
}
sort(rect.begin(), rect.end());
rect.resize(unique(rect.begin(), rect.end()) - rect.begin());
return rect.size();
}
