#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 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;
int fen[maxn];
void add(int v, int val)
{
v ++;
for (int i = v; i < maxn; i += (i & -i))
fen[i] += val;
}
int sum(int v)
{
v ++;
int s = 0;
for (int i = v; i > 0; i -= (i & -i))
s += fen[i];
return s;
}
vector < pair < int, int > > drow[maxn][maxn], dcol[maxn][maxn];
long long count_rectangles(vector<vector<int> > a)
{
n = a.size();
m = a[0].size();
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;
}*/
for (frame cur : row_frame)
{
for (int x = cur.x1; x <= cur.x2; x ++)
{
drow[x][cur.y2].push_back({x - cur.x1, cur.y2 - cur.y1});
}
}
for (frame cur : col_frame)
{
for (int y = cur.y1; y <= cur.y2; y ++)
{
dcol[cur.x2][y].push_back({cur.x2 - cur.x1, y - cur.y1});
}
}
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
sort(drow[i][j].begin(), drow[i][j].end());
sort(dcol[i][j].begin(), dcol[i][j].end());
int pt = 0;
for (int pos = 0; pos < drow[i][j].size(); pos ++)
{
while(pt < dcol[i][j].size() && drow[i][j][pos].first >= dcol[i][j][pt].first)
{
add(dcol[i][j][pt].second, 1);
///cout << sum(max(n, m)) << endl;
pt ++;
}
/**for (int j = 0; j < pt; j ++)
{
if (drow[i][j][pos].second <= dcol[i][j][j].second)
ans ++;
}*/
ans = ans + pt - sum(drow[i][j][pos].second - 1);
}
for (int pos = 0; pos < pt; pos ++)
add(dcol[i][j][pos].second, -1);
/**for (pair < int, int > col : dcol)
cout << col.first << " " << col.second << endl;
cout << "-----------" << endl;*/
/**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;
}
