#include "rect.h"
#include <bits/stdc++.h>
#define f first
#define s second
const int MAXN = 2500;
using ll = long long;
std::vector<int> right[MAXN][MAXN];
std::vector<int> down[MAXN][MAXN];
std::vector<bool> usedRight[MAXN][MAXN];
std::vector<bool> usedDown[MAXN][MAXN];
std::vector<std::pair<int, int>> rightP[MAXN][MAXN];
std::vector<std::pair<int, int>> downP[MAXN][MAXN];
std::vector<std::vector<int>> a;
int N, M;
int btsearch(std::vector<int>& vec, int v) {
if (vec.size()==0) {
return -1;
}
int low = 0;
int high = int(vec.size())-1;
while (low < high) {
int mid = (low + high)/2;
if (vec[mid] <= v) {
low = mid;
}
else if (vec[mid]) {
high = mid-1;
}
}
if (vec[low] == v) {
return low;
}
return -1;
}
void setPairs() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int id = 0;
for (int p : right[i][j]) {
if (!usedRight[i][j][id]) {
int u = i;
while (true) {
int k = btsearch(right[u+1][j], p);
if (k == -1) {
break;
}
else {
usedRight[u+1][j][k] = true;
}
u++;
}
int lst = u;
while (u >= i) {
rightP[u][j].push_back({lst, p});
u--;
}
}
id++;
}
}
}
for (int j = 0; j < M; j++) {
for (int i = 0; i < N; i++) {
int id = 0;
for (int p : down[i][j]) {
if (!usedDown[i][j][id]) {
int u = j;
while (true) {
int k = btsearch(down[i][u+1], p);
if (k == -1) {
break;
}
else {
usedDown[i][u+1][k] = true;
}
u++;
}
int lst = u;
while (u >= j) {
downP[i][u].push_back({p, lst});
u--;
}
}
id++;
}
}
}
}
void getIntervals() {
// for (int i = 1; i < N-1; i++) {
// for (int j = 1; j < M-1; j++) {
// int mx = 0;
// for (int k = j; k < M-1; k++) {
// mx = std::max(mx, a[i][k]);
// if (a[i][j-1] > mx && a[i][k+1] > mx) {
// right[i][j].insert(k);
// }
// }
// }
// }
// for (int j = 1; j < M-1; j++) {
// for (int i = 1; i < N-1; i++) {
// int mx = 0;
// for (int k = i; k < N-1; k++) {
// mx = std::max(mx, a[k][j]);
// if (a[i-1][j] > mx && a[k+1][j] > mx) {
// down[i][j].insert(k);
// }
// }
// }
// }
for (int i = 1; i < N-1; i++) {
std::stack<std::pair<int, int>> st;
st.push({a[i][0], 0});
for (int j = 1; j < M; j++) {
bool eq = false;
while (st.size() && a[i][j] >= st.top().f) {
if (st.top().s + 1 <= j-1) {
// if (!right[i][st.top().s+1].count(j-1)) {
// std::cout << "I inside"<< '\n';
// }
right[i][st.top().s+1].push_back(j-1);
}
eq = (a[i][j] == st.top().f);
st.pop();
}
if (!eq) {
if (st.size() && st.top().s + 1 <= j-1) {
// if (!right[i][st.top().s+1].count(j-1)) {
// std::cout << "I out"<< '\n';
// }
right[i][st.top().s+1].push_back(j-1);
}
}
st.push({a[i][j], j});
}
}
for (int j = 1; j < M-1; j++) {
std::stack<std::pair<int, int>> st;
st.push({a[0][j], 0});
for (int i = 1; i < N; i++) {
bool eq = false;
while (st.size() && a[i][j] >= st.top().f) {
if (st.top().s + 1 <= i-1) {
// if (!down[st.top().s+1][j].count(i-1)) {
// std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
// }
down[st.top().s+1][j].push_back(i-1);
}
eq = (a[i][j] == st.top().f);
st.pop();
}
if (!eq) {
if (st.size() && st.top().s + 1 <= i-1) {
// if (!down[st.top().s+1][j].count(i-1)) {
// std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
// }
down[st.top().s+1][j].push_back(i-1);
}
}
st.push({a[i][j], i});
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
usedDown[i][j].resize(down[i][j].size(), false);
usedRight[i][j].resize(right[i][j].size(), false);
sort(down[i][j].begin(), down[i][j].end());
sort(right[i][j].begin(), right[i][j].end());
}
}
setPairs();
}
int fen[MAXN];
void add(int val, int id) {
for (;id<MAXN;id=(id|(id+1))) {
fen[id]+=val;
}
}
int sm(int r) {
int rs = 0;
for (;r >= 0; r=(r&(r+1)) - 1) {
rs += fen[r];
}
return rs;
}
int sm(int l, int r) {
return sm(r) - sm(l-1);
}
long long count_rectangles(std::vector<std::vector<int> > board) {
a = board;
N = a.size();
M = a[0].size();
a.resize(N, std::vector<int>(M, 0));
if (N <= 2 || M <= 2) {
return 0;
}
for (int i = 1; i < N-1; i++) {
std::stack<std::pair<int, int>> st;
st.push({a[i][0], 0});
for (int j = 1; j < M; j++) {
bool eq = false;
while (st.size() && a[i][j] >= st.top().f) {
if (st.top().s + 1 <= j-1) {
// if (!right[i][st.top().s+1].count(j-1)) {
// std::cout << "I inside"<< '\n';
// }
right[i][st.top().s+1].push_back(j-1);
}
eq = (a[i][j] == st.top().f);
st.pop();
}
if (!eq) {
if (st.size() && st.top().s + 1 <= j-1) {
// if (!right[i][st.top().s+1].count(j-1)) {
// std::cout << "I out"<< '\n';
// }
right[i][st.top().s+1].push_back(j-1);
}
}
st.push({a[i][j], j});
}
}
for (int j = 1; j < M-1; j++) {
std::stack<std::pair<int, int>> st;
st.push({a[0][j], 0});
for (int i = 1; i < N; i++) {
bool eq = false;
while (st.size() && a[i][j] >= st.top().f) {
if (st.top().s + 1 <= i-1) {
// if (!down[st.top().s+1][j].count(i-1)) {
// std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
// }
down[st.top().s+1][j].push_back(i-1);
}
eq = (a[i][j] == st.top().f);
st.pop();
}
if (!eq) {
if (st.size() && st.top().s + 1 <= i-1) {
// if (!down[st.top().s+1][j].count(i-1)) {
// std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
// }
down[st.top().s+1][j].push_back(i-1);
}
}
st.push({a[i][j], i});
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
usedDown[i][j].resize(down[i][j].size(), false);
usedRight[i][j].resize(right[i][j].size(), false);
sort(down[i][j].begin(), down[i][j].end());
sort(right[i][j].begin(), right[i][j].end());
}
}
setPairs();
ll res = 0;
// std::cout << sizeof(right) + sizeof(down) + sizeof(rightP) + sizeof(downP) + sizeof(usedRight) + sizeof(usedDown) << '\n';
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
std::sort(rightP[i][j].begin(), rightP[i][j].end());
std::sort(downP[i][j].begin(), downP[i][j].end());
int u = 0;
for (auto& p : rightP[i][j]) {
while (u < downP[i][j].size() && downP[i][j][u].f <= p.f) {
add(1, downP[i][j][u].s);
u++;
}
res += sm(p.s, MAXN-1);
// for (auto& u : downP[i][j]) {
// if (u.f <= p.f && u.s >= p.s) {
// res++;
// }
// }
}
// memset(fen, 0, sizeof(fen));
while (--u>= 0) {
add(-1, downP[i][j][u].s);
}
}
}
return res;
}
