#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],arbreSom[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);
}
int calcSom(int deb,int fin) {
if (deb==fin) {
return arbreSom[deb];
}
if (deb%2==1) {
return arbreSom[deb]+calcSom(deb+1,fin);
}
if (fin%2==0) {
return arbreSom[fin]+calcSom(deb,fin-1);
}
return calcSom(deb/2,fin/2);
}
void ajout(int pos,int coeff) {
pos+=DECA;
arbreSom[pos]+=coeff;
while (pos>1) {
pos/=2;
arbreSom[pos]=arbreSom[2*pos]+arbreSom[2*pos+1];
}
}
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;
vector<tuple<int,int,int>> listeCol;
for (int i=colGau-1;i<=colDroi+1;i++) {
listeCol.push_back(make_tuple(i,1,i));
listeCol.push_back(make_tuple(limCalc[i][0]-1,-1,i));
}
sort(listeCol.begin(),listeCol.end(),[&](tuple<int,int,int> a,tuple<int,int,int> b) {
if (get<0>(a)>get<0>(b)) {
return true;
}
if (get<0>(a)<get<0>(b)) {
return false;
}
return get<0>(a)>get<0>(b);
});
for (auto k:listeCol) {
//cout<<get<0>(k)<<" "<<get<1>(k)<<" "<<get<2>(k)<<" ";
if (get<1>(k)==-1) {
ajout(get<2>(k),-1);
}
else {
if (limCalc[get<0>(k)][1]+1>=get<0>(k)+2) {
//cout<<"!";
rep+=(ll)calcSom(DECA+get<0>(k)+2,DECA+limCalc[get<0>(k)][1]+1);
}
ajout(get<0>(k),1);
}
}
//cout<<endl;
}
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;
}
