#include "rect.h"
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct node{
int x, y;
}array[7000000];
int u[2505][2505],d[2505][2505],tree1[2505][10005][2],tree2[2505][10005][2],n,m,s[2505][2505][2],l[2505][2505],st2[2505][2505][2],r[2505][2505],t[10005][2],bits[20];
int findtree1(int le,int ri,int j,int st,int en,int t,int opt)
{
if(le>en || ri<st)
{
if(opt==0)return -1;
return 5000;
}
if(st>=le && en<=ri)
{
return tree1[j][t][opt];
}
if(opt==0)return max(findtree1(le,ri,j,st,(st+en)/2,t*2,opt),findtree1(le,ri,j,(st+en)/2+1,en,t*2+1,opt));
else return min(findtree1(le,ri,j,st,(st+en)/2,t*2,opt),findtree1(le,ri,j,(st+en)/2+1,en,t*2+1,opt));
}
int findtree2(int le,int ri,int i,int st,int en,int t,int opt)
{
//cout<<le<<" "<<ri<<" "<<i<<" "<<st<<" "<<en<<" "<<opt<<" "<<t<<" "<<tree2[i][t][opt]<<endl;
if(le>en || ri<st)
{
if(opt==0)return -1;
return 5000;
}
if(st>=le && en<=ri)
{
return tree2[i][t][opt];
}
if(opt==0)return max(findtree2(le,ri,i,st,(st+en)/2,t*2,opt),findtree2(le,ri,i,(st+en)/2+1,en,t*2+1,opt));
else return min(findtree2(le,ri,i,st,(st+en)/2,t*2,opt),findtree2(le,ri,i,(st+en)/2+1,en,t*2+1,opt));
}
int find(int i,int j)
{
int x1=l[i][j],y1=u[i][j],x2=r[i][j],y2=d[i][j];
int le=l[i][j]+1,ri=r[i][j]-1;
int k=log2(ri-le+1);
//cout<<y1<<" "<<x1<<" "<<y2<<" "<<x2<<" "<<le<<" "<<ri<<endl;
int tmp=findtree2(le,ri,y1,0,m-1,1,1);
//cout<<tmp<<endl;
if( tmp < y2 ) return 0;
tmp=findtree2(le,ri,y2,0,m-1,1,0);
//cout<<tmp<<endl;
if( tmp > y1 ) return 0;
int up=u[i][j]+1,down=d[i][j]-1;
k=log2(down-up+1);
tmp=findtree1(up,down,x1,0,n-1,1,1);
//cout<<tmp<<endl;
if( tmp < x2 )return 0;
tmp=findtree1(up,down,x2,0,n-1,1,0);
//cout<<tmp<<endl;
if( tmp > x1 )return 0;
return 1;
}
bool cmp(node ax,node ay)
{
int ar[10][4];
ar[0][0]=u[ax.x][ax.y];
ar[0][1]=l[ax.x][ax.y];
ar[0][2]=d[ax.x][ax.y];
ar[0][3]=r[ax.x][ax.y];
ar[1][0]=u[ay.x][ay.y];
ar[1][1]=l[ay.x][ay.y];
ar[1][2]=d[ay.x][ay.y];
ar[1][3]=r[ay.x][ay.y];
for(int i=0;i<4;i++)
{
if(ar[0][i]<ar[1][i])return 1;
if(ar[0][i]>ar[1][i])return 0;
}
return 0;
}
void build1(int j,int st,int e,int t)
{
if(st==e)
{
tree1[j][t][0]=st2[st][j][0];
tree1[j][t][1]=st2[st][j][1];
//cout<<j<<" "<<st<<" "<<e<<" "<<t<<" "<<tree1[j][t][0]<<" "<<tree1[j][t][1]<<endl;
return ;
}
build1(j,st,(st+e)/2,t*2);
build1(j,(st+e)/2+1,e,t*2+1);
tree1[j][t][0]=max(tree1[j][t*2][0],tree1[j][t*2+1][0]);
tree1[j][t][1]=min(tree1[j][t*2][1],tree1[j][t*2+1][1]);
//cout<<j<<" "<<st<<" "<<e<<" "<<t<<" "<<tree1[j][t][0]<<" "<<tree1[j][t][1]<<endl;
return ;
}
void build2(int i,int st,int e,int t)
{
if(st==e)
{
tree2[i][t][0]=s[i][st][0];
tree2[i][t][1]=s[i][st][1];
//cout<<i<<" "<<st<<" "<<e<<" "<<t<<" "<<tree2[i][t][0]<<" "<<tree2[i][t][1]<<endl;
return ;
}
build2(i,st,(st+e)/2,t*2);
build2(i,(st+e)/2+1,e,t*2+1);
tree2[i][t][0]=max(tree2[i][t*2][0],tree2[i][t*2+1][0]);
tree2[i][t][1]=min(tree2[i][t*2][1],tree2[i][t*2+1][1]);
//cout<<i<<" "<<st<<" "<<e<<" "<<t<<" "<<tree2[i][t][0]<<" "<<tree2[i][t][1]<<endl;
return ;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n=a.size();
m=a[0].size();
for(register int i=0;i<n;i++)
{
int p=0,st=0,en=-1;
for(register int j=0;j<m;j++)
{
l[i][j]=-1;
r[i][j]=5000;
for(int k=en;k>=st;k--)
{
if(a[i][j]>t[k][0])
{
r[i][t[k][1]]=j;
en--;
}
else
{
en++;
t[en][0]=a[i][j];
t[en][1]=j;
if(a[i][j]<t[k][0])l[i][j]=t[k][1];
else l[i][j]=l[i][t[k][1]];
break;
}
}
if(en==-1)
{
en=0;
t[en][0]=a[i][j];
t[en][1]=j;
}
}
}
for(register int j=0;j<m;j++)
{
int p=0,st=0,en=-1;
for(register int i=0;i<n;i++)
{
u[i][j]=-1;
d[i][j]=5000;
for(int k=en;k>=st;k--)
{
if(a[i][j]>t[k][0])
{
d[t[k][1]][j]=i;
en--;
}
else
{
en++;
t[en][0]=a[i][j];
t[en][1]=i;
if(a[i][j]<t[k][0])u[i][j]=t[k][1];
else u[i][j]=u[t[k][1]][j];
break;
}
}
if(en==-1)
{
en=0;
t[en][0]=a[i][j];
t[en][1]=i;
}
}
}
for(register int i=0;i<n;i++)
{
int p=0,st=0,en=-1;
for(register int j=0;j<m;j++)
{
st2[i][j][0]=-1;
st2[i][j][1]=5000;
for(register int k=en;k>=st;k--)
{
if(a[i][j]>=t[k][0])
{
st2[i][t[k][1]][1]=j;
en--;
if(a[i][j]==t[k][0])
{
st2[i][j][0]=t[k][1];
en++;
t[en][0]=a[i][j];
t[en][1]=j;
break;
}
}
else
{
en++;
t[en][0]=a[i][j];
t[en][1]=j;
st2[i][j][0]=t[k][1];
break;
}
}
if(en==-1)
{
en=0;
t[en][0]=a[i][j];
t[en][1]=j;
}
}
}
for(register int j=0;j<m;j++)
{
int p=0,st=0,en=-1;
for(register int i=0;i<n;i++)
{
s[i][j][0]=-1;
s[i][j][1]=5000;
for(int k=en;k>=st;k--)
{
if(a[i][j]>=t[k][0])
{
s[t[k][1]][j][1]=i;
en--;
if(a[i][j]==t[k][0])
{
s[i][j][0]=t[k][1];
en++;
t[en][0]=a[i][j];
t[en][1]=i;
break;
}
}
else
{
en++;
t[en][0]=a[i][j];
t[en][1]=i;
s[i][j][0]=t[k][1];
break;
}
}
if(en==-1)
{
en=0;
t[en][0]=a[i][j];
t[en][1]=i;
}
}
}
//cout<<st2[4][16][0][1]<<endl;
bits[0]=1;
for(int i=0;i<m;i++)
{
build1(i,0,n-1,1);
}
//cout<<endl;
for(int j=0;j<n;j++)
{
build2(j,0,m-1,1);
}
int ans=0;
int cnt=0;
for(register int i=0;i<n;i++)
{
for(register int j=0;j<m;j++)
{
if(u[i][j]==-1 || d[i][j]==5000 || l[i][j]==-1 || r[i][j]==5000)continue;
//if((a[i-1][j]==a[i][j] && i!=1) || (a[i][j-1]==a[i][j] && j!=1))continue;
cnt++;
array[cnt].x=i;
array[cnt].y=j;
}
}
sort(array+1,array+cnt+1,cmp);
//cout<<cnt<<endl;
for(register int i=1;i<=cnt;i++)
{
int x=array[i].x,y=array[i].y,x1=array[i-1].x,y1=array[i-1].y;
if(u[x][y]==u[x1][y1] && d[x][y]==d[x1][y1] && l[x][y]==l[x1][y1] && r[x][y]==r[x1][y1])continue;
//cout<<x<<" "<<y<<endl;
int tmp=find(x,y);
if(tmp==1)
//cout<<u[x][y]+1<<" "<<l[x][y]+1<<" "<<d[x][y]-1<<" "<<r[x][y]-1<<endl;
//cout<<endl;
ans+=tmp;
}
return ans;
}
