#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 stk[N];
int top;
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;
}
}
/// cout << " : " << r1 - 1 << " " << r2 - 1 << " " << c1 - 1 << " " << c2 - 1 << "\n";
solutions.push_back({r1, c1, r2, c2});
}
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;
stk[0] = 0;
for (int j = 1; j <= m; j++)
{
while (top && a[i][stk[top]] < a[i][j])
{
top--;
}
st[i][j - 1] = stk[top] + 1;
stk[++top] = j;
}
top = 0;
stk[0] = m + 1;
for (int j = m; j >= 1; j--)
{
while (top && a[i][stk[top]] < a[i][j])
{
top--;
}
dr[i][j + 1] = stk[top] - 1;
stk[++top] = j;
}
}
for (int j = 1; j <= m; j++)
{
top = 0;
stk[0] = 0;
for (int i = 1; i <= n; i++)
{
while (top && a[stk[top]][j] < a[i][j])
{
top--;
}
sus[i - 1][j] = stk[top] + 1;
stk[++top] = i;
}
top = 0;
stk[0] = n + 1;
for (int i = n; i >= 1; i--)
{
while (top && a[stk[top]][j] < a[i][j])
{
top--;
}
jos[i + 1][j] = stk[top] - 1;
stk[++top] = i;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
check(sus[i][j], st[i][j], i, j);
check(sus[i][j], j, i, dr[i][j]);
check(i, st[i][j], jos[i][j], j);
check(i, j, jos[i][j], dr[i][j]);
}
}
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;
}
