#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
struct Fenwick {
vector<int> sum;
int n;
Fenwick(int _n) : n(_n) {
sum.resize(n + 1);
}
void modify(int x, int d) {
x += 1;
while (x <= n) {
sum[x] += d;
x += x & -x;
}
}
int get(int x) {
x += 1;
int res = 0;
while (x > 0) {
res += sum[x];
x -= x & -x;
}
return res;
}
};
vector<vector<vector<array<int, 2>>>> calc_ranges(vector<vector<int>> A) {
int N = int(A.size());
int M = int(A[0].size());
vector<vector<vector<array<int, 2>>>> res(N, vector<vector<array<int, 2>>>(M));
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;
res[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);
}
}
return res;
}
long long count_rectangles(std::vector<std::vector<int> > A) {
int N = int(A.size());
int M = int(A[0].size());
auto row_ranges = calc_ranges(A);
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];
}
}
auto temp = calc_ranges(temp_A);
vector<vector<vector<array<int, 2>>>> col_ranges(N, vector<vector<array<int, 2>>>(M));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
col_ranges[i][j] = temp[j][i];
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
debug(i, j, row_ranges[i][j]);
debug(i, j, col_ranges[i][j]);
}
}
vector<Fenwick> fenw(N, Fenwick(N));
long long ans = 0;
for (int l = 0; l < M - 1; ++l) {
vector<vector<array<int, 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<int, 2>>> rem(M);
vector<pair<int, int>> add;
for (int i = 0; i < N; ++i) {
for (auto[d, ending] : col_ranges[i][l + 1]) {
fenw[i + 1].modify(d - 1, +1);
rem[min(M - 1, ending + 1)].push_back({i + 1, d - 1});
add.emplace_back(i + 1, d - 1);
}
}
debug(l, query, add, rem);
for (int r = l + 2; r < M; ++r) {
for (auto[u, d] : query[r]) {
ans += fenw[u].get(d);
}
for (auto[u, d] : rem[r]) {
fenw[u].modify(d, -1);
}
}
debug(ans);
}
return ans;
}
