#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> get_bune(vector<int> v)
{
vector<pair<int,int>> bune;
deque<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});
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];
long long count_rectangles(std::vector<std::vector<int>> a)
{
long long rez=0;
for(int i=1;i+1<a.size();i++)
{
bune_pe_rand[i] = get_bune(a[i]);
}
for(int i=1;i+1<a[0].size();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++)
{
vector<pair<int,int>> candidati = bune_pe_rand[sus];
for(int jos=sus;jos+1<a.size();jos++)
{
vector<pair<int,int>> newc;
int pozc=0,pozr=0;
while(pozc < candidati.size() && pozr < bune_pe_rand[jos].size())
{
if(candidati[pozc] == bune_pe_rand[jos][pozr])
{
newc.push_back(candidati[pozc]);
pozc++;
pozr++;
}
else if(candidati[pozc] < bune_pe_rand[jos][pozr])
{
pozc++;
}
else
{
pozr++;
}
}
candidati = newc;
for(auto [x,y]:candidati)
{
int cnt=0;
for(int c:coloane_bune[sus][jos])
if(x<=c && c<=y)
cnt++;
if(cnt == y-x+1)
rez++;
}
}
}
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
*/
