#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
const int N = 2500 + 7;
int n;
int m;
int a[N][N];
int st[N][N];
int dr[N][N];
int sus[N][N];
int jos[N][N];
int stv[N];
int top;
struct KEKMAN
{
int x;
int l;
int r;
};
bool operator < (KEKMAN a, KEKMAN b)
{
if (a.x != b.x)
{
return a.x < b.x;
}
else
{
return a.r < b.r;
}
}
bool operator == (KEKMAN a, KEKMAN b)
{
return (a.x == b.x && a.r == b.r);
}
vector<KEKMAN> rows;
vector<KEKMAN> cols;
bool good(int r, int c)
{
return (1 < r && 1 < c && r < n && c < m);
}
struct T
{
int a;
int b;
int c;
int d;
};
bool operator < (T f, T s)
{
if (f.a != s.a) return f.a < s.a;
if (f.b != s.b) return f.b < s.b;
if (f.c != s.c) return f.c < s.c;
return f.d < s.d;
}
bool operator != (T f, T s)
{
if (f.a != s.a) return 1;
if (f.b != s.b) return 1;
if (f.c != s.c) return 1;
if (f.d != s.d) return 1;
return 0;
}
vector<T> solutions;
void check(int r1, int c1, int r2, int c2)
{
if (!good(r1, c1) || !good(r2, c2))
{
return;
}
if (r1 > r2 || c1 > c2)
{
return;
}
for (int r = r1; r <= r2; r++)
{
if (dr[r][c1] != c2 && st[r][c2] != c1)
{
return;
}
}
for (int c = c1; c <= c2; c++)
{
if (jos[r1][c] != r2 && sus[r2][c] != r1)
{
return;
}
}
solutions.push_back({r1, c1, r2, c2});
}
int lx[N][N];
int rx[N][N];
int ly[N][N];
int ry[N][N];
long long count_rectangles(vector<vector<int>> b)
{
n = (int) b.size();
m = (int) b[0].size();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
a[i][j] = b[i - 1][j - 1];
}
}
for (int i = 1; i <= n; i++)
{
top = 0;
stv[0] = 0;
for (int j = 1; j <= m; j++)
{
while (top && a[i][stv[top]] < a[i][j])
{
top--;
}
st[i][j - 1] = stv[top] + 1;
stv[++top] = j;
}
top = 0;
stv[0] = m + 1;
for (int j = m; j >= 1; j--)
{
while (top && a[i][stv[top]] < a[i][j])
{
top--;
}
dr[i][j + 1] = stv[top] - 1;
stv[++top] = j;
}
}
for (int j = 1; j <= m; j++)
{
top = 0;
stv[0] = 0;
for (int i = 1; i <= n; i++)
{
while (top && a[stv[top]][j] < a[i][j])
{
top--;
}
sus[i - 1][j] = stv[top] + 1;
stv[++top] = i;
}
top = 0;
stv[0] = n + 1;
for (int i = n; i >= 1; i--)
{
while (top && a[stv[top]][j] < a[i][j])
{
top--;
}
jos[i + 1][j] = stv[top] - 1;
stv[++top] = i;
}
}
for (int i = 2; i < n; i++)
{
for (int j = 2; j < m; j++)
{
if (1 < st[i][j] && st[i][j] <= j)
{
rows.push_back({i, st[i][j], j});
}
if (dr[i][j] < m && j <= dr[i][j])
{
rows.push_back({i, j, dr[i][j]});
}
if (1 < sus[i][j] && sus[i][j] <= i)
{
cols.push_back({j, sus[i][j], i});
}
if (jos[i][j] < n && i <= jos[i][j])
{
cols.push_back({j, i, jos[i][j]});
}
}
}
sort(rows.begin(), rows.end());
sort(cols.begin(), cols.end());
int pos = 0;
for (int r2 = 1; r2 <= n; r2++)
{
for (int c2 = 1; c2 <= m; c2++)
{
KEKMAN it = {r2, 0, c2};
while (pos < (int) rows.size() && rows[pos] < it)
{
pos++;
}
if (pos < (int) rows.size() && rows[pos] == it)
{
int i = pos, j;
while (pos + 1 < (int) rows.size() && rows[pos + 1] == it)
{
pos++;
}
j = pos;
lx[r2][c2] = i;
rx[r2][c2] = j;
pos++;
}
else
{
lx[r2][c2] = -1;
rx[r2][c2] = -1;
}
}
}
pos = 0;
for (int c2 = 1; c2 <= m; c2++)
{
for (int r2 = 1; r2 <= n; r2++)
{
KEKMAN it = {c2, 0, r2};
while (pos < (int) cols.size() && cols[pos] < it)
{
pos++;
}
if (pos < (int) cols.size() && cols[pos] == it)
{
int i = pos, j;
while (pos + 1 < (int) cols.size() && cols[pos + 1] == it)
{
pos++;
}
j = pos;
ly[r2][c2] = i;
ry[r2][c2] = j;
pos++;
}
else
{
ly[r2][c2] = -1;
ry[r2][c2] = -1;
}
}
}
for (int r = 1; r <= n; r++)
{
for (int c = 1; c <= m; c++)
{
if (lx[r][c] != -1 && ly[r][c] != -1)
{
for (int i = lx[r][c]; i <= rx[r][c]; i++)
{
int c1 = rows[i].l;
for (int j = ly[r][c]; j <= ry[r][c]; j++)
{
int r1 = cols[j].l;
check(r1, c1, r, c);
}
}
}
}
}
if (solutions.empty())
{
return 0;
}
sort(solutions.begin(), solutions.end());
int sol = 1;
for (int i = 1; i < (int) solutions.size(); i++)
{
sol += (solutions[i] != solutions[i - 1]);
}
return sol;
}
