#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi19/d1/debug.h"
#else
#define debug(...) void(37)
#endif
constexpr int mxN = 2501;
vector<array<short, 2>> col_ranges[mxN][mxN];
vector<array<short, 2>> row_ranges[mxN][mxN];
struct Fenwick {
short sum[mxN][mxN];
Fenwick() {
memset(sum, mxN * mxN * sizeof(short), 0);
}
void modify(int i, int x, int d) {
x += 1;
while (x < mxN) {
sum[i][x] += d;
x += x & -x;
}
}
int get(int i, int x) {
x += 1;
int res = 0;
while (x > 0) {
res += sum[i][x];
x -= x & -x;
}
return res;
}
};
using RT = vector<vector<vector<array<short, 2>>>>;
void calc_ranges(vector<vector<int>> A, bool inv) {
int N = int(A.size());
int M = int(A[0].size());
int sn = N, sm = M;
if (inv) {
swap(sn, sm);
}
//RT res(sn, vector<vector<array<short, 2>>>(sm));
vector<vector<array<int, 2>>> last(M, vector<array<int, 2>>(M, array<int, 2>{}));
for (int i = N - 1; i >= 0; --i) {
auto Add = [&](int l, int r) {
if (l + 1 == r) {
return;
}
if (last[l][r][0] != i + 1) {
last[l][r][1] = i;
}
last[l][r][0] = i;
(inv ? col_ranges[l][i] : row_ranges[i][l]).push_back({r, last[l][r][1]});
};
vector<int> st;
for (int j = M - 1; j >= 0; --j) {
bool eq = false;
while (!st.empty() && A[i][st.back()] <= A[i][j]) {
eq |= A[i][st.back()] == A[i][j];
Add(j, st.back());
st.pop_back();
}
if (!st.empty() && !eq) {
Add(j, st.back());
}
st.push_back(j);
}
}
}
long long count_rectangles(std::vector<std::vector<int> > A) {
int N = int(A.size());
int M = int(A[0].size());
calc_ranges(A, false);
vector<vector<int>> temp_A(M, vector<int>(N));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
temp_A[j][i] = A[i][j];
}
}
calc_ranges(temp_A, true);
/*
auto temp = calc_ranges(temp_A);
RT col_ranges(N, vector<vector<array<short, 2>>>(M));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
col_ranges[i][j] = temp[j][i];
}
}
*/
Fenwick fenw;
long long ans = 0;
for (int l = 0; l < M - 1; ++l) {
vector<vector<array<short, 2>>> query(M);
for (int i = 0; i < N; ++i) {
for (auto[r, ending] : row_ranges[i][l]) {
query[r].push_back({i, ending});
}
}
vector<vector<array<short, 2>>> rem(M);
for (int i = 0; i < N; ++i) {
for (auto[d, ending] : col_ranges[i][l + 1]) {
fenw.modify(i + 1, d - 1, +1);
rem[min(M - 1, ending + 1)].push_back({i + 1, d - 1});
}
}
for (int r = l + 2; r < M; ++r) {
for (auto[u, d] : query[r]) {
ans += fenw.get(u, d);
}
for (auto[u, d] : rem[r]) {
fenw.modify(u, d, -1);
}
}
debug(ans);
}
return ans;
}
