#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
using ll=long long;
const int TAILLE_MAX=2505,DECA=(1<<12),INFINI=1000*1000*1000;
ll rep;
int nbLig,nbCol;
int val[TAILLE_MAX][TAILLE_MAX];
int limite[TAILLE_MAX][TAILLE_MAX][4];
int limCalc[TAILLE_MAX][2];
int arbreMin[TAILLE_MAX][2*DECA],arbreMax[TAILLE_MAX][2*DECA];
vector<int> possi;
set<int> enCours;
set<int>::iterator it;
vector<int> prop[TAILLE_MAX][TAILLE_MAX];
int calcMin(int tab,int deb,int fin) {
if (deb==fin) {
return arbreMin[tab][deb];
}
if (deb%2==1) {
return min(arbreMin[tab][deb],calcMin(tab,deb+1,fin));
}
if (fin%2==0) {
return min(arbreMin[tab][fin],calcMin(tab,deb,fin-1));
}
return calcMin(tab,deb/2,fin/2);
}
int calcMax(int tab,int deb,int fin) {
if (deb==fin) {
return arbreMax[tab][deb];
}
if (deb%2==1) {
return max(arbreMax[tab][deb],calcMax(tab,deb+1,fin));
}
if (fin%2==0) {
return max(arbreMax[tab][fin],calcMax(tab,deb,fin-1));
}
return calcMax(tab,deb/2,fin/2);
}
void calc(int ligHaut,int ligBas,int colGau,int colDroi) {
//cout<<ligHaut<<" "<<ligBas<<" "<<colGau<<" "<<colDroi<<" : ";
for (int i=colGau-1;i<=colDroi+1;i++) {
limCalc[i][0]=calcMax(i,DECA+ligHaut,DECA+ligBas);
limCalc[i][1]=calcMin(i,DECA+ligHaut,DECA+ligBas);
//cout<<i<<" "<<limCalc[i][0]<<" "<<limCalc[i][1]<<" ";
}
//cout<<endl;
for (int i=colGau;i<=colDroi;i++) {
for (int j=i;j<=colDroi;j++) {
if (limCalc[i-1][1]>=j and limCalc[j+1][0]<=i) {
//cout<<"! "<<ligHaut<<" "<<ligBas<<" "<<i<<" "<<j<<endl;
rep++;
}
}
}
}
ll count_rectangles(vector<vector<int>> a) {
nbLig=a.size();
nbCol=a[0].size();
if (nbLig<=2 or nbCol<=2) {
return 0;
}
for (int i=0;i<nbLig;i++) {
for (int j=0;j<nbCol;j++) {
val[i][j]=a[i][j];
}
}
for (int i=0;i<nbLig;i++) {
enCours.clear();
enCours.insert(-1);
possi.clear();
for (int j=0;j<nbCol;j++) {
possi.push_back(j);
}
sort(possi.begin(),possi.end(),[&](int a,int b) {
if (val[i][a]>val[i][b]) {
return true;
}
if (val[i][a]<val[i][b]) {
return false;
}
return a<b;
});
for (int j:possi) {
it=enCours.upper_bound(j);
it--;
limite[i][j][0]=(*it)+1;
//cout<<i<<" "<<j<<" : "<<limite[i][j][0]<<endl;
enCours.insert(j);
}
enCours.clear();
enCours.insert(nbCol);
sort(possi.begin(),possi.end(),[&](int a,int b) {
if (val[i][a]>val[i][b]) {
return true;
}
if (val[i][a]<val[i][b]) {
return false;
}
return a>b;
});
for (int j:possi) {
it=enCours.upper_bound(j);
limite[i][j][1]=(*it)-1;
//cout<<i<<" "<<j<<" : "<<limite[i][j][0]<<endl;
enCours.insert(j);
}
}
for (int j=0;j<nbCol;j++) {
enCours.clear();
enCours.insert(-1);
possi.clear();
for (int i=0;i<nbLig;i++) {
possi.push_back(i);
}
sort(possi.begin(),possi.end(),[&](int a,int b) {
if (val[a][j]>val[b][j]) {
return true;
}
if (val[a][j]<val[b][j]) {
return false;
}
return a<b;
});
for (int i:possi) {
it=enCours.upper_bound(i);
it--;
limite[i][j][2]=(*it)+1;
//cout<<i<<" "<<j<<" : "<<limite[i][j][0]<<endl;
enCours.insert(i);
}
enCours.clear();
enCours.insert(nbLig);
sort(possi.begin(),possi.end(),[&](int a,int b) {
if (val[a][j]>val[b][j]) {
return true;
}
if (val[a][j]<val[b][j]) {
return false;
}
return a>b;
});
for (int i:possi) {
it=enCours.upper_bound(i);
limite[i][j][3]=(*it)-1;
//cout<<i<<" "<<j<<" : "<<limite[i][j][0]<<endl;
enCours.insert(i);
}
}
int deb,pos;
for (int i=0;i<nbCol;i++) {
for (int j=0;j<2*DECA;j++) {
arbreMin[i][j]=nbCol-1;
arbreMax[i][j]=0;
}
for (int j=0;j<nbLig;j++) {
arbreMin[i][DECA+j]=limite[j][i][1];
arbreMax[i][DECA+j]=limite[j][i][0];
}
for (int j=DECA-1;j>0;j--) {
arbreMin[i][j]=min(arbreMin[i][2*j],arbreMin[i][2*j+1]);
arbreMax[i][j]=max(arbreMax[i][2*j],arbreMax[i][2*j+1]);
}
}
possi.clear();
for (int i=0;i<nbLig;i++) {
possi.push_back(i);
}
int lig;
for (int col=1;col<nbCol-1;col++) {
enCours.clear();
enCours.insert(-INFINI);
enCours.insert(INFINI);
sort(possi.begin(),possi.end(),[&](int a,int b) {
if (val[a][col]>val[b][col]) {
return true;
}
if (val[a][col]<val[b][col]) {
return false;
}
return a<b;
});
//cout<<col<<" : ";
for (int i=0;i<nbLig;i++) {
lig=possi[i];
//cout<<lig<<" ";
it=enCours.upper_bound(lig);
if ((*it)!=INFINI and (*it)-lig>1 and (i==nbLig-1 or val[possi[i]][col]>val[possi[i+1]][col] or possi[i+1]>(*it))) {
//cout<<"! "<<lig+1<<" "<<(*it)-1<<" "<<col<<endl;
prop[lig+1][(*it)-1].push_back(col);
}
it--;
if ((*it)!=-INFINI and lig-(*it)>1) {
prop[(*it)+1][lig-1].push_back(col);
//cout<<"! "<<(*it)+1<<" "<<lig-1<<" "<<col<<endl;
}
enCours.insert(lig);
}
//cout<<endl;
}
for (int ligHaut=1;ligHaut<nbLig-1;ligHaut++) {
for (int ligBas=ligHaut;ligBas<nbLig-1;ligBas++) {
prop[ligHaut][ligBas].push_back(INFINI);
pos=0;
while (prop[ligHaut][ligBas][pos]!=INFINI) {
deb=pos;
while (prop[ligHaut][ligBas][pos]!=INFINI and prop[ligHaut][ligBas][pos+1]==prop[ligHaut][ligBas][pos]+1) {
pos++;
}
calc(ligHaut,ligBas,prop[ligHaut][ligBas][deb],prop[ligHaut][ligBas][pos]);
pos++;
}
}
}
return rep;
}
