#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];
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);
}
/**for (int i = 0; i < n; i ++)
{
for (int j1 = 0; j1 < m; j1 ++)
{
mrow[i][j1][j1] = h[i][j1];
for (int j2 = j1 + 1; j2 < m; j2 ++)
{
mrow[i][j1][j2] = max(mrow[i][j1][j2 - 1], h[i][j2]);
}
}
}
for (int j = 0; j < m; j ++)
for (int i1 = 0; i1 < n; i1 ++)
{
mcol[j][i1][i1] = h[i1][j];
for (int i2 = i1 + 1; i2 < n; i2 ++)
{
mcol[j][i1][i2] = max(mcol[j][i1][i2 - 1], h[i2][j]);
}
}*/
/**cout << "-----------" << endl;
for (int i = 0; i < n; i ++, cout << endl)
for (int j = 0; j < m; j ++)
cout << h[i][j] << " ";
cout << "-----------" << endl;*/
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;
}
