#include "rect.h"
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, w[2600][2600], T[2600];
vector<int>Right[2600][2600], Down[2600][2600];
int st[2600], RR[2600], LL[2600];
void PreCalc(int n) {
int i, top = 0;
for (i = 1; i <= n; i++)RR[i] = LL[i] = 0;
for (i = 1; i <= n; i++) {
while (top && T[st[top]] <= T[i]) {
RR[st[top]] = i;
top--;
}
st[++top] = i;
}
top = 0;
for (i = n; i >= 1; i--) {
while (top && T[st[top]] <= T[i]) {
LL[st[top]] = i;
top--;
}
st[++top] = i;
}
}
int last[2600][2600], CC[2600][2600];
int lastH[2600], CH[2600];
struct point {
int x, y, ck;
bool operator<(const point &p)const {
return x < p.x;
}
}U[10100];
int BIT[2600];
void Add(int a, int b) {
while (a <= m) {
BIT[a] += b;
a += (a&-a);
}
}
int Sum(int a) {
int r = 0;
while (a) {
r += BIT[a];
a -= (a&-a);
}
return r;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
int i, j;
for (i = 0; i < n; i++)for (j = 0; j < m; j++)w[i + 1][j + 1] = a[i][j];
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
T[j] = w[i][j];
}
PreCalc(m);
for (j = 1; j <= m; j++) {
if (RR[j] && RR[j]>j+1)Right[i][j+1].push_back(RR[j]-1);
if (LL[j] && LL[j]<j-1 && RR[LL[j]] != j)Right[i][LL[j] + 1].push_back(j - 1);
}
}
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
T[j] = w[j][i];
}
PreCalc(n);
for (j = 1; j <= n; j++) {
if (RR[j] && RR[j] > j + 1)Down[j + 1][i].push_back(RR[j] - 1);
if (LL[j] && LL[j] < j - 1 && RR[LL[j]] != j)Down[LL[j] + 1][i].push_back(j - 1);
}
}
long long res = 0;
for (i = n; i >= 1; i--) {
for (j = 1; j <= n; j++)lastH[j] = CH[j] = 0;
for (j = m; j >= 1; j--) {
for (auto &t : Right[i][j]) {
if (last[j][t] != i + 1)CC[j][t] = 0;
CC[j][t]++;
last[j][t] = i;
}
for (auto &t : Down[i][j]) {
if (lastH[t] != j + 1)CH[t]=0;
CH[t]++;
lastH[t] = j;
}
int cnt = 0;
for (auto &t : Right[i][j]) {
U[cnt++] = { i,t,1 };
U[cnt++] = { i + CC[j][t],t,-1 };
}
sort(U, U + cnt);
sort(Down[i][j].begin(), Down[i][j].end());
int pv = 0;
for (auto &t : Down[i][j]) {
while (pv < cnt && U[pv].x <= t) {
Add(U[pv].y, U[pv].ck);
pv++;
}
res += Sum(j + CH[t] - 1);
}
while (pv < cnt) {
Add(U[pv].y, U[pv].ck);
pv++;
}
}
}
return res;
}
