#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2510;
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);
//cout << i << " --- " << j << " -- " << mx << endl;
if (mx < h[1][i - 1] && mx < h[1][j + 1])
ans ++;
}
return ans;
}
bool check_row(int row, int left, int right)
{
int mx = mrow[row].query(left, right);
if (mx < h[row][left - 1] && mx < h[row][right + 1])
return true;
return false;
}
bool check_col(int col, int up, int down)
{
int mx = mcol[col].query(up, down);
if (mx < h[up - 1][col] && mx < h[down + 1][col])
return true;
return false;
}
struct frame
{
short x1, x2, y1, y2;
frame(short _x1 = 0, short _x2 = 0, short _y1 = 0, short _y2 = 0)
{
x1 = _x1;
x2 = _x2;
y1 = _y1;
y2 = _y2;
}
};
vector < frame > row_frame, col_frame;
vector < frame > row_cell[maxn][maxn], col_cell[maxn][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];
vector < frame > last_row;
int cnt = 0;
int ans = 0;
for (int row = 1; row < n - 1; row ++)
{
set < pair < int, int > > st;
for (int left_col = 0; left_col < m; left_col ++)
{
int right_col = left_col + 1;
while(right_col < m && h[row][left_col] > h[row][right_col])
right_col ++;
///cout << "here " << row << " " << left_col << " " << right_col << endl;
if (right_col != m && left_col + 1 < right_col)
{
cnt ++;
///cout << h[row][left_col] << " " << h[row][right_col] << endl;
st.insert({left_col + 1, right_col - 1});
}
}
for (int right_col = m - 1; right_col > 0; right_col --)
{
int left_col = right_col - 1;
while(left_col >= 0 && h[row][right_col] > h[row][left_col])
left_col --;
///cout << row << " :: " << left_col << " :: " << right_col << endl;
if (left_col >= 0 && h[row][right_col] < h[row][left_col] &&
left_col + 1 < right_col)
{
cnt ++;
//cout << "row " << row << " " << left_col + 1 << " :: " << right_col - 1 << endl;
st.insert({left_col + 1, right_col - 1});
}
}
vector < frame > new_row;
for (int i = 0; i < last_row.size(); i ++)
{
pair < int, int > cur = make_pair(last_row[i].y1, last_row[i].y2);
if (st.find(cur) == st.end())
{
row_frame.push_back(last_row[i]);
}
else
{
last_row[i].x2 ++;
new_row.push_back(last_row[i]);
st.erase(cur);
}
}
for (pair < int, int > cur : st)
{
new_row.push_back(frame(row, row, cur.first, cur.second));
}
last_row = new_row;
}
for (frame cur : last_row)
row_frame.push_back(cur);
vector < frame > last_col;
for (int col = 1; col < m - 1; col ++)
{
set < pair < int, int > > st;
for (int left_row = 0; left_row < n; left_row ++)
{
int right_row = left_row + 1;
while(right_row < n && h[left_row][col] > h[right_row][col])
right_row ++;
///cout << "here " << row << " " << left_col << " " << right_col << endl;
if (right_row != n && left_row + 1 < right_row)
{
cnt ++;
///cout << h[row][left_col] << " " << h[row][right_col] << endl;
st.insert({left_row + 1, right_row - 1});
}
}
for (int right_row = n - 1; right_row > 0; right_row --)
{
int left_row = right_row - 1;
while(left_row >= 0 && h[right_row][col] > h[left_row][col])
left_row --;
///cout << row << " :: " << left_col << " :: " << right_col << endl;
if (left_row >= 0 && h[right_row][col] < h[left_row][col] &&
left_row + 1 < right_row)
{
cnt ++;
//cout << "row " << row << " " << left_col + 1 << " :: " << right_col - 1 << endl;
st.insert({left_row + 1, right_row - 1});
}
}
vector < frame > new_col;
for (int i = 0; i < last_col.size(); i ++)
{
pair < int, int > cur = make_pair(last_col[i].x1, last_col[i].x2);
if (st.find(cur) == st.end())
{
col_frame.push_back(last_col[i]);
}
else
{
last_col[i].y2 ++;
new_col.push_back(last_col[i]);
st.erase(cur);
}
}
for (pair < int, int > cur : st)
{
new_col.push_back(frame(cur.first, cur.second, col, col));
}
last_col = new_col;
}
for (frame cur : last_col)
col_frame.push_back(cur);
/**for (frame cur : last_col)
{
cout << "frame " << cur.x1 << " " << cur.x2 << " " << cur.y1 << " " << cur.y2 << endl;
}*/
if (cnt > 4 * n * m)
exit(0);
for (frame cur : row_frame)
{
for (int x = cur.x1; x <= cur.x2; x ++)
{
row_cell[x][cur.y2].push_back(cur);
}
}
for (frame cur : col_frame)
{
for (int y = cur.y1; y <= cur.y2; y ++)
{
col_cell[cur.x2][y].push_back(cur);
}
}
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
vector < pair < int, int > > drow, dcol;
for (frame row : row_cell[i][j])
{
drow.push_back({i - row.x1, j - row.y1});
}
for (frame col : col_cell[i][j])
{
dcol.push_back({i - col.x1, j - col.y1});
}
for (pair < int, int > row : drow)
for (pair < int, int > col : dcol)
{
if (row.first >= col.first && col.second >= row.second)
ans ++;
}
/**for (frame row : row_cell[i][j])
for (frame col : col_cell[i][j])
{
bool tf = false;
if (col.x1 >= row.x1 && col.x2 <= row.x2 &&
row.y1 >= col.y1 && row.y2 <= col.y2)
tf = true;
if (tf)
{
ans ++;
}
}*/
}
}
return ans;
}
