#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
struct cell
{
int i,j,st;
};
bool cmp(cell a1,cell a2)
{
return a1.st<a2.st;
}
int a[3005][3005],n,m,in[10005],cur=1,miv[100000000],mav[100000000],mih[100000000],mah[100000000],omiv,omav,omih,omah;
map<int,int>mv[3005],mh[3005];
map<long long int,int>otg;
cell c[10000000];
void convert(long long int i1,long long int j1,long long int i2,long long int j2)
{
long long int nn=n,mm=m;
otg[(i1*mm+j1)*(nn*mm)+i2*mm+j2]=1;
}
void build(int l,int r,int h)
{
in[h]=cur;
cur+=10000;
if(l==r)return;
int mid=(l+r)/2;
build(l,mid,h*2);
build(mid+1,r,h*2+1);
}
void update2(int l,int r,int q,int h,int vmi,int vma,int xmi,int xma,int con)
{
if(l>q||r<q)return;
int cur=h+con,le=h*2+con,re=h*2+1+con;
if(l==r)
{
miv[cur]=vmi;
mav[cur]=vma;
mih[cur]=xmi;
mah[cur]=xma;
return;
}
int mid=(l+r)/2;
update2(l,mid,q,h*2,vmi,vma,xmi,xma,con);
update2(mid+1,r,q,h*2+1,vmi,vma,xmi,xma,con);
mav[cur]=max(mav[le],mav[re]);
miv[cur]=min(miv[le],miv[re]);
mah[cur]=max(mah[le],mah[re]);
mih[cur]=min(mih[le],mih[re]);
}
void update1(int l,int r,int q1,int q2,int h,int vmi,int vma,int xmi,int xma)
{
if(l>q1||r<q1)return;
update2(1,m,q2,1,vmi,vma,xmi,xma,in[h]);
if(l==r)
{
return;
}
int mid=(l+r)/2;
update1(l,mid,q1,q2,h*2,vmi,vma,xmi,xma);
update1(mid+1,r,q1,q2,h*2+1,vmi,vma,xmi,xma);
}
void query2(int l,int r,int ql,int qr,int h,int con)
{
if(l>qr||r<ql)return;
int cur=h+con;
if(l>=ql&&r<=qr)
{
omiv=min(omiv,miv[cur]);
omav=max(omav,mav[cur]);
omih=min(omih,mih[cur]);
omah=max(omah,mah[cur]);
return;
}
int mid=(l+r)/2;
query2(l,mid,ql,qr,h*2,con);
query2(mid+1,r,ql,qr,h*2+1,con);
}
void query1(int l,int r,int ql1,int qr1,int ql2,int qr2,int h)
{
if(l>qr1||r<ql1)return;
if(l>=ql1&&r<=qr1)
{
query2(1,m,ql2,qr2,1,in[h]);
return;
}
int mid=(l+r)/2;
query1(l,mid,ql1,qr1,ql2,qr2,h*2);
query1(mid+1,r,ql1,qr1,ql2,qr2,h*2+1);
}
void resh(int i,int j,int st)
{
//cout<<i<<" "<<j<<" "<<st<<endl;
auto h=mh[i].upper_bound(j);
int cmah=h->first;
h--;
int cmih=h->first;
h=mv[j].upper_bound(i);
int cmav=h->first;
h--;
int cmiv=h->first;
cmiv++;
cmih++;
cmav--;
cmah--;
if(i==5&&j==3)
{
/*cout<<endl<<endl;
cout<<"--------"<<endl;
cout<<cmiv<<" "<<cmav<<" "<<cmih<<" "<<cmah<<endl<<endl;*/
}
update1(1,n,i,j,1,cmiv,cmav,cmih,cmah);
if(cmiv>1&&cmav<n&&cmih>1&&cmah<m)
{
omiv=1e9;
omih=1e9;
omav=0;
omah=0;
//cout<<"!"<<endl;
query1(1,n,cmiv,cmav,cmih,cmah,1);
if(i==5&&j==3)
{
//cout<<omiv<<" "<<omav<<" "<<omih<<" "<<omah<<endl<<endl<<endl;
}
if(cmih==omih&&cmah==omah&&cmiv==omiv&&cmav==omav)
{
/*cout<<i<<" "<<j<<" "<<st<<endl;
cout<<cmiv<<" "<<cmav<<" "<<cmih<<" "<<cmah<<endl;
cout<<omiv<<" "<<omav<<" "<<omih<<" "<<omah<<endl;
cout<<"???"<<endl;*/
convert(cmiv,cmih,cmav,cmah);
}
}
}
long long int count_rectangles(vector<vector<int> > A)
{
n=A.size();
m=A[0].size();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
a[i+1][j+1]=A[i][j];
c[i*m+j+1].i=i+1;
c[i*m+j+1].j=j+1;
c[i*m+j+1].st=a[i+1][j+1];
}
}
build(1,n,1);
sort(c+1,c+n*m+1,cmp);
//cout<<endl<<endl;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m+1;j++)
{
mh[i][j]=1;
}
}
for(int j=1;j<=m;j++)
{
for(int i=0;i<=n+1;i++)
{
mv[j][i]=1;
}
}
int to=1;
for(int i=1;i<=n*m;i++)
{
while(to<=n*m&&c[to].st==c[i].st)
{
mv[c[to].j].erase(c[to].i);
mh[c[to].i].erase(c[to].j);
to++;
}
resh(c[i].i,c[i].j,c[i].st);
}
return otg.size();
}
