#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<array<int, 2>> ed[2510];
vector<pair<int, int>> qr[2510];
ll fen[2510];
void upd(int u, int k) {
for (; u <= 2500; u += (u & -u)) fen[u] += (ll) k;
}
ll query(int u) {
ll res = 0;
for (; u; u -= (u & -u)) res += fen[u];
return res;
}
ll count_rectangles(std::vector<std::vector<int32_t>> inp) {
int n = inp.size(), m = inp[0].size();
ll ans = 0;
vector<vector<int>> a(n+1, vector<int> (m+1));
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i][j] = inp[i-1][j-1];
vector<vector<vector<int>>> h(m+1, vector<vector<int>> (m+1));
vector<vector<vector<int>>> v(n+1, vector<vector<int>> (n+1));
for (int i = 1; i <= n; i++) {
stack<int> st;
for (int j = 1; j <= m; j++) {
bool eq = 0;
while (!st.empty() && a[i][st.top()] <= a[i][j]) {
if (st.top() + 1 < j && !eq) h[st.top() + 1][j - 1].push_back(i);
if (a[i][st.top()] == a[i][j]) eq = true;
st.pop();
}
if (!st.empty() && st.top() + 1 < j && !eq) h[st.top() + 1][j - 1].push_back(i);
st.push(j);
}
}
for (int j = 1; j <= m; j++) {
stack<int> st;
for (int i = 1; i <= n; i++) {
bool eq = 0;
while (!st.empty() && a[st.top()][j] <= a[i][j]) {
if (st.top() + 1 < i && !eq) v[st.top() + 1][i - 1].push_back(j);
if (a[st.top()][j] == a[i][j]) eq = true;
st.pop();
}
if (!st.empty() && st.top() + 1 < i && !eq) v[st.top() + 1][i - 1].push_back(j);
st.push(i);
}
}
vector<vector<vector<array<int, 3>>>> rrect(n+1, vector<vector<array<int, 3>>> (m+1));
vector<vector<vector<array<int, 3>>>> crect(n+1, vector<vector<array<int, 3>>> (m+1));
for (int c1 = 1; c1 <= m; c1++) {
for (int c2 = c1; c2 <= m; c2++) {
vector<pair<int, int>> pr;
for (int& row : h[c1][c2]) {
// printf("strip: row = %d, columns = %d, %d\n", row, c1, c2);
if (pr.empty() || pr.back().second + 1 != row) pr.push_back({row, row});
else pr.back().second++;
}
for (auto& [lb, rb] : pr) for (int i = lb; i <= rb; i++) crect[i][c1].push_back({c2, i, rb});
}
}
h.clear();
for (int r1 = 1; r1 <= n; r1++) {
for (int r2 = r1; r2 <= n; r2++) {
vector<pair<int, int>> pr;
for (int& col : v[r1][r2]) {
// printf("strip: column = %d, rows = %d, %d\n", col, r1, r2);
if (pr.empty() || pr.back().second + 1 != col) pr.push_back({col, col});
else pr.back().second++;
}
for (auto& [lb, rb] : pr) for (int i = lb; i <= rb; i++) rrect[r1][i].push_back({r2, i, rb});
}
}
v.clear();
for (int r1 = 1; r1 <= n; r1++) {
for (int c1 = 1; c1 <= m; c1++) {
vector<int> crit;
for (auto& [r2, lb, rb] : rrect[r1][c1]) {
crit.push_back(r2);
qr[r2].push_back({lb, rb});
}
for (auto& [c2, lb, rb] : crect[r1][c1]) {
crit.push_back(lb);
crit.push_back(rb + 1);
ed[lb].push_back({1, c2});
ed[rb + 1].push_back({0, c2});
}
sort(crit.begin(), crit.end());
crit.erase(unique(crit.begin(), crit.end()), crit.end());
for (auto& ti : crit) {
for (auto& [x, y] : ed[ti]) {
if (x) upd(y, 1);
else upd(y, -1);
}
for (auto& [x, y] : qr[ti]) ans += query(y) - query(x-1);
// cout << r1 << " " << c1 << " " << ans << '\n';
ed[ti].clear();
qr[ti].clear();
}
}
}
return ans;
}
