#include <bits/stdc++.h>
#include "rect.h"
#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define eb emplace_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()
const int MAX = 2505 ;
using namespace std ;
int N , M ;
vector<int> esq, dir, getFreq, lastVisit , marca ;
void solve( vector< vector<int > > &grid, vector< vector< vector<pii> > > &toPut )
{
int tamLinha = sz( grid[0] ) ;
esq.clear() ;
esq.shrink_to_fit() ;
dir.clear() ;
dir.shrink_to_fit() ;
getFreq.clear() ;
getFreq.shrink_to_fit() ;
lastVisit.clear() ;
lastVisit.shrink_to_fit() ;
marca.clear() ;
marca.shrink_to_fit() ;
lp(i,0,tamLinha + 5)
{
esq.eb(0) ;
dir.eb(0) ;
getFreq.eb(0) ;
lastVisit.eb(0) ;
marca.eb(0) ;
}
for(int i = 1 ; i < sz(grid) - 1 ; i++ )
{
lp(j,0,tamLinha)
esq[j] = dir[j] = -1 , marca[j] = 0 ;
for(int j = tamLinha - 2; j > 0 ; j-- )
{
int x = j+1 ;
while( x != -1 && grid[i][x]<= grid[i][j] )
{
if( grid[i][x] == grid[i][j] ) marca[j] = true ;
x = dir[x] ;
}
dir[j] = x ;
}
for(int j = 1 ; j < tamLinha-1 ; j++ )
{
int x = j-1 ;
while(x != -1 && grid[i][x] <= grid[i][j] )
x = esq[x] ;
esq[j] = x ;
}
lp(j,1,tamLinha-1)
if( marca[j] == 0 && esq[j] != -1 && dir[j] != -1 )
toPut[ i ][ esq[j]+1 ].emplace_back( mk(dir[j]-1 , i) ) ;
}
for(int j = 1 ; j < tamLinha-1 ; j++ )
{
lp(i,0,tamLinha+4) getFreq[i] = lastVisit[i] = -1 ;
for(int i = sz(grid) - 2 ; i >= 1 ; i-- )
for(auto &e : toPut[i][j] )
{
if( e.ff < 0 || e.ff > tamLinha - 1 ) continue ;
if( lastVisit[e.ff] != i+1 ) getFreq[e.ff] = i ;
e.ss = getFreq[e.ff] ;
lastVisit[e.ff] = i ;
}
}
}
vector< vector<int> > gridCerto , gridRota ;
vector< vector< vector<pii> > > auxCerto, auxRota ;
int bit[MAX] ;
void upd(int pos, int idx) { for(int i = pos ; i < MAX ; i += (i&-i)) bit[i] += idx ; }
int qry(int pos)
{
int tot = 0 ;
for(int i = pos ; i > 0 ; i -= (i&-i)) tot += bit[i] ;
return tot ;
}
ll count_rectangles( vector<vector<int> > mat )
{
if( sz(mat) < 3 || sz(mat[0]) < 3 ) return 0LL ;
N = sz(mat) ;
M = sz( mat[0] ) ;
lp(i,0,N)
{
gridCerto.emplace_back(*(new vector<int>)) ;
auxCerto.emplace_back(*(new vector< vector<pii> >)) ;
lp(j,0,M)
{
gridCerto[i].emplace_back( mat[i][j] ) ;
auxCerto[i].emplace_back( *(new vector<pii>) ) ;
}
}
lp(i,0,M)
{
gridRota.emplace_back( *(new vector<int>) ) ;
auxRota.emplace_back(*(new vector< vector<pii> >)) ;
lp(j,0,N)
{
gridRota[i].emplace_back( mat[j][i] ) ;
auxRota[i].emplace_back( *(new vector<pii>) ) ;
}
}
solve(gridCerto, auxCerto ) ;
solve( gridRota, auxRota );
ll ans = 0LL ;
lp(i,1,N-1)
lp(j,1,M-1)
{
sort( all(auxCerto[i][j]) ) ;
sort( all(auxRota[j][i]) , [&](pii i, pii j) { return i.ss < j.ss ; }) ;
for(auto e : auxRota[j][i] ) upd( e.ff , 1 ) ;
int ptr = 0 ;
for(auto e : auxCerto[i][j] )
{
while( ptr < sz( auxRota[j][i] ) && auxRota[j][i][ptr].ss < e.ff )
{
upd( auxRota[j][i][ptr].ff , -1 ) ;
ptr++ ;
}
ans += (ll)( qry(e.ss) ) ;
}
while( ptr < sz(auxRota[j][i]) )
{
upd(auxRota[j][i][ptr].ff, -1 ) ;
ptr++ ;
}
}
return ans ;
}
