#include "rect.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<set>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vp vector<pi>
#define ss set<pi>
void print(vvi &L) {
cerr << "{";
for (auto i : L) {
cerr << "{";
for (auto j : i) cerr << j << ", ";
cerr << "},\n";
}
cerr << endl;
}
void print(vi &L) {
cerr << "{";
for (auto i : L) cerr << i << ", ";
cerr << "}" << endl;
}
void print(ss &S) {
cerr << "{";
for (auto i : S) {
cerr << "{" << i.first << ", " << i.second << "}, ";
}
cerr << "}\n";
}
ll count_rectangles(vector<vector<int>> B) {
if (B.size() <= 2 || B[0].size() <= 2) return 0;
vvi CL(B.size(), vi(B[0].size(), -1));
vvi CR = CL, RT = CL, RB = CL;
vp L;
for (int j = 0; j < B.size(); j++) {
//cerr << "j : " << j << endl;
L.clear();
for (int i = B[0].size()-1; i > -1; i--) {
//cerr << "i : " << i << endl;
while (L.size() && L.back().first < B[j][i]) L.pop_back();
;
//cerr << "oink" << endl;
if (L.size()) CL[j][i] = L.back().second;
else CL[j][i] = B[0].size()-1;
L.push_back({B[j][i], i});
}
}
for (int j = 0; j < B.size(); j++) {
//cerr << "j : " << j << endl;
L.clear();
for (int i = 0; i < B[0].size(); i++) {
//cerr << "i : " << i << endl;
while (L.size() && L.back().first < B[j][i]) L.pop_back();
;
//cerr << "oink" << endl;
if (L.size()) CR[j][i] = L.back().second;
else CR[j][i] = 0;
L.push_back({B[j][i], i});
}
}
for (int i = 0; i < B[0].size(); i++) {
//cerr << "j : " << j << endl;
L.clear();
for (int j = B.size()-1; j > -1; j--) {
//cerr << "i : " << i << endl;
while (L.size() && L.back().first < B[j][i]) L.pop_back();
;
//cerr << "oink" << endl;
if (L.size()) RT[j][i] = L.back().second;
else RT[j][i] = B.size()-1;
L.push_back({B[j][i], j});
}
}
for (int i = 0; i < B[0].size(); i++) {
//cerr << "j : " << j << endl;
L.clear();
for (int j = 0; j < B.size(); j++) {
//cerr << "i : " << i << endl;
while (L.size() && L.back().first < B[j][i]) L.pop_back();
;
//cerr << "oink" << endl;
if (L.size()) RB[j][i] = L.back().second;
else RB[j][i] = 0;
L.push_back({B[j][i], j});
}
}
/*
cerr << "CL\n";
print(CL);
cerr << "CR\n";
print(CR);
cerr << "RT\n";
print(RT);
cerr << "RB\n";
print(RB);
//*/
ll t = 0;
/*
for (int i = 0; i < B.size(); i++) {
for (int j = 0; j < B[0].size(); j++) {
//t += (B[i][j]);
}
}//*/
ss S2;
for (int r1 = 0; r1 < B[0].size(); r1++) {
for (int r2 = r1+2; r2 < B[0].size(); r2++) {
S2.insert({r1, r2});
}
}
for (int c1 = 0; c1 < B.size(); c1++) {
vi L2(B[0].size(), 1);
ss S = S2;
for (int c2 = c1+2; c2 < B.size(); c2++) {
//cerr << "\n" << "c1 : " << c1 << ", c2 : " << c2 << ", t : " << t << endl;
vi L(B[0].size(), 0);
int oi = 1;
for (int r1 = 0; r1 < B[0].size(); r1++) {
if (RT[c1][r1] >= c2 && RB[c2][r1] <= c1) {
L[r1] = oi;
continue;
}
oi++;
}
L2 = L;
//cerr << c1 << " " << c2 << " : ";
//print(L);
ss S3;
for (auto i = S.begin(); i != S.end(); i++) {
int r1 = (*i).first, r2 = (*i).second;
/*
if (L[r1+1] != L[r2-1] || L[r1+1] == 0) {
S3.insert({r1, r2});
continue;
}//*/
if (CL[c2-1][r1] >= r2 && CR[c2-1][r2] <= r1) {
if (L[r1+1] != L[r2-1] || L[r1+1] == 0) continue;
t += 1;
continue;
}
S3.insert({r1, r2});
}
//print(S3);
for (auto i : S3) {
S.erase(i);
}
//print(S);
}
}
return t;
}
