#include "rect.h"
#include<set>
#include<vector>
#include<algorithm>
#include<utility>
#define MAXN 2505
using namespace std;
int N,M,A[MAXN][MAXN];
vector<pair<int,int> > Hor[MAXN][MAXN], Vert[MAXN][MAXN];
set<pair<int,int> > HorM[MAXN], VertM[MAXN]; //unordered?
vector<pair<int,int> > S;
class fenwick {
int ft[MAXN + 5];
public:
void add(int v, int p) {
for (int i=p; i<=MAXN; i+=i&(-i)) {ft[i]+=v;}
}
int ask(int p) {
int res = 0;
for (int i=p; i>0; i-=i&(-i)) {res+=ft[i];}
return(res);
}
} BIT;
void pairs() {
for (int i=1; i<=N; i++) { //init horizontal
while (S.size()) {S.pop_back();}
for (int j=1; j<=M; j++) {
while(S.size() && S.back().first <= A[i][j]) {
if (j - S.back().second > 1) {HorM[i].insert({S.back().second, j});}
S.pop_back();
}
if (S.size() && j - S.back().second > 1) {HorM[i].insert({S.back().second, j});}
S.push_back({A[i][j], j});
}
}
for (int j=1; j<=M; j++) {
while (S.size()) {S.pop_back();}
for (int i=1; i<=N; i++) {
while (S.size() && S.back().first <= A[i][j]) {
if (i - S.back().second > 1) {VertM[j].insert({S.back().second,i});}
S.pop_back();
}
if (S.size() && i - S.back().second > 1) {VertM[j].insert({S.back().second,i});}
S.push_back({A[i][j], i});
}
}
for (int i=N; i>=1; i--) {
while (HorM[i].size()) {
int pt = i;
pair <int,int> p = *HorM[i].begin();
while (HorM[pt].find(p) != HorM[pt].end()) {
Hor[pt][p.first].push_back({p.second, i}); //i is goes up to
HorM[pt].erase(p), pt--;
}
}
}
for (int j=M; j>=1; j--) {
while (VertM[j].size()) {
int pt = j;
pair <int,int> p = *VertM[j].begin();
while (VertM[pt].find(p) != VertM[pt].end()) {
Vert[p.first][pt].push_back({j, p.second});
VertM[pt].erase(p), pt--;
}
}
}
for (int i=1; i<=N; i++) {
for (int j=1; j<=M; j++) {
sort(Hor[i][j].begin(), Hor[i][j].end());
sort(Vert[i][j].begin(), Vert[i][j].end());
}
}
}
long long count_rectangles(vector<vector<int> > a) {
long long ans = 0;
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]; //zero index
}
}
pairs();
for (int i=1; i<=N; i++) {
for (int j=1; j<=M; j++) {
//(i,j) top left
int pt1 = Hor[i+1][j].size()-1, pt2 = Vert[i][j+1].size()-1; //go (i,j+1) for vert and (i+1,j) for hor
while (pt1 >= 0 || pt2 >= 0) {
if (pt1 == -1 || (pt2 >= 0 && Hor[i+1][j][pt1].first >= Vert[i][j+1][pt2].first)) {
BIT.add(1, Vert[i][j+1][pt2].second);
pt2--;
} else {
ans += (long long) BIT.ask(Hor[i+1][j][pt1].second+1) - BIT.ask(i+1);
pt1--;
}
}
for (auto v: Vert[i][j+1]) {
BIT.add(-1, v.second);
}
}
}
return(ans);
}
