#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sz(x) (int)x.size()
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
typedef signed i32;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vi32> vvi32;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
long long count_rectangles(vvi a)
{
int n = sz(a); // h
int m = sz(a[0]); // w
vvvi validUp(n, vvi(m, vi(m)));
vvvi validDown(n, vvi(m, vi(m)));
vvvi validL(m, vvi(n, vi(n)));
vvvi validR(m, vvi(n, vi(n))); // omwisselen voor cache friendlyness?
vvi minL(n, vi(m, 1e9)), minU(n, vi(m, 1e9)), maxR(n, vi(m, -1)), maxD(n, vi(m, -1));
for (int c = 1; c < m - 1; c++)
{
for (int r = 1; r < n - 1; r++)
{
for (int c1 = c; c1 > 0; c1--)
{
if (a[r][c1] >= a[r][c + 1])
break;
minL[r][c] = c1;
}
for (int c2 = c; c2 < m - 1; c2++)
{
if (a[r][c2] >= a[r][c - 1])
break;
maxR[r][c] = c2;
}
for (int r1 = r; r1 > 0; r1--)
{
if (a[r1][c] >= a[r + 1][c])
break;
minU[r][c] = r1;
}
for (int r2 = r; r2 < n - 1; r2++)
{
if (a[r2][c] >= a[r - 1][c])
break;
maxD[r][c] = r2;
}
}
}
for (int c = 1; c < m - 1; c++)
{
for (int r1 = 1; r1 < n - 1; r1++)
{
int mnL = 0;
int mxR = m;
for (int r2 = r1; r2 < n - 1; r2++)
{
mnL = max(mnL, minL[r2][c]);
mxR = min(mxR, maxR[r2][c]);
validL[c][r1][r2] = mxR;
validR[c][r1][r2] = mnL;
}
}
}
for (int r = 1; r < n - 1; r++)
{
for (int c1 = 1; c1 < m - 1; c1++)
{
int mnU = 0;
int mxD = n;
for (int c2 = c1; c2 < m - 1; c2++)
{
mnU = max(mnU, minU[r][c2]);
mxD = min(mxD, maxD[r][c2]);
validUp[r][c1][c2] = mxD;
validDown[r][c1][c2] = mnU;
}
}
}
int treeM = 1;
while (treeM < m)
treeM *= 2;
vector<vector<vvi>> tree(n, vvvi(n, vvi(treeM * 2)));
// validR is geen voolean meer. het hangt af van l.
// merge sort tree bouwen op validR, return count <= l
for (int r1 = 1; r1 < n - 1; r1++)
{
for (int r2 = r1; r2 < n - 1; r2++)
{
for (int c = 1; c < m - 1; c++)
{
tree[r1][r2][treeM + c] = {validR[c][r1][r2]};
}
rev(treeM, i)
{
merge(ALL(tree[r1][r2][2 * i]),
ALL(tree[r1][r2][2 * i + 1]),
back_inserter(tree[r1][r2][i]));
}
}
}
auto query = [&](auto &&self, int r1, int r2, int i, int l, int r, int ql, int qr, int v) -> int
{
int mid = (l + r) / 2;
if (qr < l || r < ql)
return 0;
if (ql <= l && r <= qr)
{
long int res = upper_bound(ALL(tree[r1][r2][i]), v) - tree[r1][r2][i].begin();
return (int)res;
}
return self(self, r1, r2, 2 * i, l, mid, ql, qr, v) +
self(self, r1, r2, 2 * i + 1, mid + 1, r, ql, qr, v);
};
long long res = 0;
for (int c = 1; c < m - 1; c++)
{
for (int r1 = 1; r1 < n - 1; r1++)
{
for (int r2 = r1; r2 < n - 1; r2++)
{
int mxR = validL[c][r1][r2];
if (mxR == -1)
break;
int lo = c, hi = mxR;
int ans = -1;
while (hi >= lo)
{
int c2 = (lo + hi) / 2;
if (validUp[r1][c][c2] >= r2 && validDown[r2][c][c2] <= r1)
{
ans = c2;
lo = c2 + 1;
}
else
{
hi = c2 - 1;
}
}
if (ans == -1)
continue;
res += query(query, r1, r2, 1, 0, treeM - 1, c, ans, c);
}
}
}
return res;
}
