#pragma GCC optimize("O3,unroll-loops")
#include "rect.h"
#include<iostream>
#include<algorithm>
using namespace std;
vector<pair<int,int>> get_bune(vector<int> v)
{
vector<pair<int,int>> bune;
vector<int> dq;
for(int i=0;i<v.size();i++)
{
while(!dq.empty() && v[i] > v[dq.back()])
{
if(dq.back()+1 <= i-1)
bune.push_back({dq.back()+1,i-1});
dq.pop_back();
}
if(!dq.empty() && dq.back()+1 <= i-1)
bune.push_back({dq.back()+1,i-1});
if(!dq.empty() && v[dq.back()] == v[i])
dq.pop_back();
dq.push_back(i);
}
//sort(bune.begin(),bune.end());
return bune;
}
vector<pair<int,int>> bune_pe_rand[2505];
vector<int> coloane_bune[2505][2505];
vector<int> randuri_bune[2505][2505],primu[2505][2505];
int poz_rbune[2505][2505];
int aib[2505][2505],m;
int qry(int x, int y)
{
x++;
y++;
int aux=0;
for(int i=x;i<=m;i+=(i&(-i)))
for(int j=y;j>0;j-=(j&(-j)))
aux += aib[i][j];
return aux;
}
void upd(int x, int y, int newv)
{
x++;
y++;
for(int i=x;i>0;i-=(i&(-i)))
for(int j=y;j<=m;j+=(j&(-j)))
aib[i][j] += newv;
}
vector<pair<int,int>> scoase[2505];
long long count_rectangles(std::vector<std::vector<int>> a)
{
m = a[0].size();
long long rez=0;
for(int i=1;i+1<a.size();i++)
{
bune_pe_rand[i] = get_bune(a[i]);
for(auto [x,y]:bune_pe_rand[i])
randuri_bune[x][y].push_back(i);
}
for(int x=1;x+1<m;x++)
{
for(int y=x;y+1<m;y++)
{
if(randuri_bune[x][y].empty())
continue;
primu[x][y].resize(randuri_bune[x][y].size() + 2);
int ult = a.size();
if(randuri_bune[x][y].back() != (int)a.size() - 2)
ult = randuri_bune[x][y].back() + 1;
primu[x][y][randuri_bune[x][y].size()] = ult;
for(int i=randuri_bune[x][y].size()-1;i>0;i--)
{
if(randuri_bune[x][y][i] != randuri_bune[x][y][i-1] + 1)
ult = randuri_bune[x][y][i-1] + 1;
primu[x][y][i] = ult;
}
}
}
for(int i=1;i+1<m;i++)
{
vector<int> aux;
for(int j=0;j<a.size();j++)
aux.push_back(a[j][i]);
vector<pair<int,int>> bune = get_bune(aux);
for(auto [x,y]:bune)
coloane_bune[x][y].push_back(i);
}
for(int sus=1;sus+1<a.size();sus++)
{
for(int jos=sus;jos<=a.size();jos++)
scoase[jos].clear();
for(auto [x,y]:bune_pe_rand[sus])
{
upd(x,y,+1);
while(randuri_bune[x][y][poz_rbune[x][y]] < sus)
poz_rbune[x][y]++;
scoase[primu[x][y][poz_rbune[x][y]+1]].push_back({x,y});
}
for(int jos=sus;jos+1<a.size();jos++)
{
//for(int i=0;i<scoase[jos].size();i++) upd(scoase[jos][i].first,scoase[jos][i].second,-1);
for(auto [x,y]:scoase[jos]) upd(x,y,-1);
//for(pair<int,int> x:scoase[jos]) upd(x.first,x.second,-1);
/*int ult=0;
for(int i=0;i<coloane_bune[sus][jos].size();i++)
{
if(i == (int)coloane_bune[sus][jos].size() - 1 || coloane_bune[sus][jos][i] + 1 != coloane_bune[sus][jos][i+1])
{
int le = coloane_bune[sus][jos][ult], ri = coloane_bune[sus][jos][i];
rez += qry(le,ri);
ult = i+1;
}
}*/
if(!coloane_bune[sus][jos].empty())
{
int ult = coloane_bune[sus][jos][0];
int prec = ult-1;
for(int x:coloane_bune[sus][jos])
{
if(x != prec+1)
{
rez += qry(ult,prec);
ult = x;
}
prec = x;
}
rez += qry(ult,prec);
}
}
for(auto [x,y]:scoase[a.size()]) upd(x,y,-1);
}
return rez;
}
/*
ne fixam linia de sus
apoi mergem cu linia de jos in jos, o sa avem la inceput O(N) perechi de coloane candidate
cand adaugam o linie in jos o sa dezactivam niste perechi de coloane
trebuie sa verificam pt fiecare (sus,jos) care coloane sunt bune
asta o sa fie O(N^2), pt ca fiecare coloana o sa apara in O(N) (sus,jos)-uri
facem un dsu in care tinem si candidatii de perechi de coloane si cam asta e tot sper
*/
