#pragma once
#include <bits/stdc++.h>
#include "rect.h"
#define fi first
#define se second
using namespace std;
const int MX = 2505;
vector<int> row[MX], col[MX];
vector<pair<int, int>> pair_row, pair_col;
int bit[MX];
int lst_row[MX][MX], cnt_row[MX][MX];
int lst_col[MX][MX], cnt_col[MX][MX];
void update(int u, int v)
{
for (; u < MX; u += u & -u)
bit[u] += v;
}
int query(int u)
{
int ret = 0;
for (; u > 0; u -= u & -u)
ret += bit[u];
return ret;
}
pair<int, int> process(int l, int r, int cur, int lst[MX][MX], int cnt[MX][MX])
{
if (lst[l][r] != cur - 1)
cnt[l][r] = 0;
cnt[l][r]++; lst[l][r] = cur;
return {r - l - 1, cnt[l][r]};
}
long long find_ans(vector<pair<int, int>> &row, vector<pair<int, int>> &col)
{
long long ans = 0;
for (pair<int, int> &v : col)
swap(v.fi, v.se);
sort(row.begin(), row.end(), greater<pair<int, int>>());
sort(col.begin(), col.end(), greater<pair<int, int>>());
int pt = 0;
for (pair<int, int> &v : row)
{
for (; pt < col.size() && v.fi <= col[pt].fi; pt++)
update(col[pt].se, 1);
ans += query(v.se);
}
for (int i = 0; i < pt; i++)
update(col[i].se, -1);
return ans;
}
long long count_rectangles(vector<vector<int>> a)
{
bool eq;
int m = a.size(), n = a[0].size();
long long ans = 0;
for (int i = 0; i < m; i++)
row[i] = {0};
for (int i = 0; i < n; i++)
col[i] = {0};
for (int i = 0; i < m - 1; i++)
for (int j = 0; j < n - 1; j++)
{
eq = false; pair_row.clear();
while (!row[i].empty())
{
int u = row[i].back();
if (u < j && !eq)
pair_row.push_back(process(u, j + 1, i, lst_row, cnt_row));
eq = (a[i][u] == a[i][j + 1]);
if (a[i][u] <= a[i][j + 1])
row[i].pop_back();
else
break;
}
row[i].push_back(j + 1);
eq = false; pair_col.clear();
while (!col[j].empty())
{
int u = col[j].back();
if (u < i && !eq)
pair_col.push_back(process(u, i + 1, j, lst_col, cnt_col));
eq = (a[u][j] == a[i + 1][j]);
if (a[u][j] <= a[i + 1][j])
col[j].pop_back();
else
break;
}
col[j].push_back(i + 1);
ans += find_ans(pair_row, pair_col);
}
return ans;
}
