#pragma GCC optimize("Ofast")
#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 int N = 2505;
struct segtree{
vector<int> ele;
int mode;
int n;
void init(int sz, int md){
mode = md;
n = sz;
ele.resize(2 * n);
}
void upd(int id, int v){
id += n;
ele[id] = v;
id /= 2;
while(id > 0){
if(mode == 0) ele[id] = min(ele[id * 2], ele[id * 2 + 1]);
else ele[id] = max(ele[id * 2], ele[id * 2 + 1]);
id /= 2;
}
}
int get(int l, int r){
l += n;
r += n;
int res = -1;
if(mode == 0) res = 5000;
while(l <= r){
if(l % 2 == 1){
if(mode == 0) res = min(res, ele[l]);
else res = max(res, ele[l]);
l ++ ;
}
if(r % 2 == 0){
if(mode == 0) res = min(res, ele[r]);
else res = max(res, ele[r]);
r -- ;
}
l /= 2;
r /= 2;
}
return res;
}
};
segtree L[N], R[N], U[N], D[N];
int Lf[N][N], Rf[N][N], Uf[N][N], Df[N][N];
bool is_valid(int i1, int j1, int i2, int 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]){
mono.pop_back();
}
if(!mono.empty())
Lf[i][j] = mono.back();
mono.push_back(j);
}
mono.clear();
for(int j = 0; j < m ; j ++ ){
while(!mono.empty() && e[i][mono.back()] < e[i][j]){
mono.pop_back();
}
if(mono.empty()){
L[j].upd(i, -1);
}
else{
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]){
mono.pop_back();
}
if(!mono.empty())
Rf[i][j] = mono.back();
mono.push_back(j);
}
mono.clear();
for(int j = m - 1; j >= 0; j -- ){
while(!mono.empty() && e[i][mono.back()] < e[i][j]){
mono.pop_back();
}
if(mono.empty())
R[j].upd(i, 5000);
else
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]){
mono.pop_back();
}
if(!mono.empty())
Uf[i][j] = mono.back();
mono.push_back(i);
}
mono.clear();
for(int i = 0 ; i < n; i ++ ){
while(!mono.empty() && e[mono.back()][j] < e[i][j])
mono.pop_back();
if(mono.empty())
U[i].upd(j, -1);
else
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])
mono.pop_back();
if(!mono.empty())
Df[i][j] = mono.back();
mono.push_back(i);
}
mono.clear();
for(int i = n - 1; i >= 0 ; i -- ){
while(!mono.empty() && e[mono.back()][j] < e[i][j])
mono.pop_back();
if(mono.empty())
D[i].upd(j, 5000);
else
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();
}
