#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 710;
int n, m;
int h[maxn][maxn], lg[maxn];
struct sparse_table
{
vector < vector < int > > table;
sparse_table(){};
void build_sparse_table(vector < int > &values)
{
int n = values.size();
table.resize(lg[n]);
for (int i = 0; i < lg[n]; i ++)
table[i].resize(n);
for (int i = 0; i < n; i ++)
table[0][i] = values[i];
for (int j = 1; j < lg[n]; j ++)
for (int i = 0; i < n - (1 << j); i ++)
{
table[j][i] = max(table[j - 1][i],
table[j - 1][i + (1 << (j - 1))]);
}
}
int query(int left, int right)
{
int len = lg[right - left + 1] - 1;
return max(table[len][left], table[len][right - (1 << len) + 1]);
}
};
sparse_table mrow[maxn], mcol[maxn];
int check_array(int left, int right)
{
///cout << left << " : " << right << endl;
int ans = 0;
for (int i = left; i <= right; i ++)
for (int j = i; j <= right; j ++)
{
int mx = mrow[1].query(i, j);
if (mx < h[1][i - 1] && mx < h[1][j + 1])
ans ++;
}
return ans;
}
long long count_rectangles(vector<vector<int> > a)
{
n = a.size();
m = a[0].size();
for (int i = 1; i <= max(n, m); i ++)
lg[i] = lg[i / 2] + 1;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
h[i][j] = a[i][j];
for (int i = 0; i < n; i ++)
{
///mrow[i].build_sparse_table(a[i]);
vector < int > values;
for (int j = 0; j < m; j ++)
values.push_back(a[i][j]);
mrow[i].build_sparse_table(values);
}
for (int j = 0; j < m; j ++)
{
vector < int > values;
for (int i = 0; i < n; i ++)
values.push_back(a[i][j]);
mcol[j].build_sparse_table(values);
}
if (n == 3)
{
int ans = 0, len = 0;
for (int j = 1; j < m - 1; j ++)
{
///cout << j << " :: " << len << endl;
if (h[1][j] < h[0][j] && h[1][j] < h[2][j])
len ++;
else
{
if (len > 0)
ans += check_array(j - len, j - 1);
}
}
if (len > 0)
ans +=check_array(m - len, m - 1);
return ans;
}
int ans = 0;
for (int i = 1; i < n - 1; i ++)
for (int j = 1; j < m - 1; j ++)
for (int x = i; x < n - 1; x ++)
for (int y = j; y < m - 1; y ++)
{
/**int i = 4;
int x = 4;
int j = 2;
int y = 3;*/
bool tf = true;
for (int dx = 0; dx <= x - i && tf; dx ++)
{
int mx = mrow[i + dx].query(j, y), cx = i + dx;
//cout << mx << " " << i + dx << " " << j << " " << y << endl;
if (mx >= h[cx][j - 1] || mx >= h[cx][y + 1])
tf = false;
}
for (int dy = 0; dy <= y - j && tf; dy ++)
{
int mx = mcol[j + dy].query(i, x), cy = j + dy;
//cout << mx << " " << h[i - 1][cy] << " " << h[x + 1][cy] << endl;
if (mx >= h[i - 1][cy] || mx >= h[x + 1][cy])
tf = false;
}
/**for (int dx = 0; dx <= x - i && tf; dx ++)
for (int dy = 0; dy <= y - j && tf; dy ++)
{
int cx = i + dx, cy = j + dy;
if (h[cx][cy] >= h[cx][j - 1] || h[cx][cy] >= h[cx][y + 1])
tf = false;
if (i == 1 && j == 1 && x == 2 && y == 1)
{
//cout << dx << " : " << dy << " : " << tf << endl;
///cout << h[cx][cy] << " -- " << h[cx][j - 1] << " -- " << h[cx][y + 1] << endl;
}
if (h[cx][cy] >= h[i - 1][cy] || h[cx][cy] >= h[x + 1][cy])
tf = false;
}*/
if (tf)
{
///cout << i << " " << j << " " << x << " " << y << endl;
ans ++;
}
}
return ans;
}
