#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ii, int> inter;
const int len = 2505, mx = 2500;
int mat[len][len], po[len], n, m;
int bit[len][len];
vector<inter> row[len], col[len];
void upd(int i, int j, int v){
while (j <= mx)
bit[i][j] += v, j += j&(-j);
}
int ask(int i, int j){
int ans = 0;
while (j > 0)
ans += bit[i][j], j -= j&(-j);
return ans;
}
vector<inter> make_inter(vector<int> vec){
vector<inter> res;
vector<int> stck;
for (int i = 0; i < vec.size(); i++){
while (!stck.empty() && vec[i] > vec[stck.back()])
stck.pop_back();
if (!stck.empty() && stck.back() < i-1)
res.pb(mp(mp(stck.back()+1, i-1), 1));
stck.pb(i);
}
stck.clear();
for (int i = (int)vec.size()-1; i >= 0; i--){
while (!stck.empty() && vec[i] > vec[stck.back()])
stck.pop_back();
if (!stck.empty() && stck.back() > i+1)
res.pb(mp(mp(i+1, stck.back()-1), 1));
stck.pb(i);
}
sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
bool comp1(inter a, inter b){
return (a.se > b.se);
}
bool comp2(inter a, inter b){
return (a.fi.se-a.fi.fi > b.fi.se-b.fi.fi);
}
ll count_rectangles(vector<vector<int> > M) {
n = M.size(), m = M[0].size();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
mat[i][j] = M[i][j];
for (int i = n-1; i >= 0; i--){
vector<int> vec;
for (int j = 0; j < m; j++)
vec.pb(mat[i][j]);
row[i] = make_inter(vec);
for (int k = 0, l = 0; k < row[i].size(); k++){
while (l < row[i+1].size() && row[i+1][l].fi < row[i][k].fi)
l++;
if (l < row[i+1].size() && row[i+1][l].fi == row[i][k].fi)
row[i][k].se += row[i+1][l].se;
}
/*printf("row#%d\n", i);
for (auto cur: row[i])
printf("[(%d, %d), %d] ", cur.fi.fi, cur.fi.se, cur.se);
printf("\n");*/
}
for (int j = m-1; j >= 0; j--){
vector<int> vec;
for (int i = 0; i < n; i++)
vec.pb(mat[i][j]);
col[j] = make_inter(vec);
for (int k = 0, l = 0; k < col[j].size(); k++){
while (l < col[j+1].size() && col[j+1][l].fi < col[j][k].fi)
l++;
if (l < col[j+1].size() && col[j+1][l].fi == col[j][k].fi)
col[j][k].se += col[j+1][l].se;
}
/*printf("col#%d\n", j);
for (auto cur: col[j])
printf("[(%d, %d), %d] ", cur.fi.fi, cur.fi.se, cur.se);
printf("\n");*/
}
ll ans = 0;
for (int j = 0; j < m; j++)
po[j] = 0;
for (int row1 = 0; row1 < n; row1++){
vector<inter> vec;
for (int j = 0; j < m; j++)
while (po[j] < col[j].size() && col[j][po[j]].fi.fi == row1)
vec.pb(mp(mp(j, col[j][po[j]].fi.se), col[j][po[j]].se)), po[j]++;
sort(vec.begin(), vec.end(), comp1);
sort(row[row1].begin(), row[row1].end(), comp2);
//printf("after sort: row1 = %d\n", row1);
int j = 0;
for (int i = 0; i < row[row1].size(); i++){
int col1 = row[row1][i].fi.fi, col2 = row[row1][i].fi.se;
int row2 = row1+row[row1][i].se-1;
while (j < vec.size() && vec[j].se >= col2-col1+1)
upd(vec[j].fi.fi, vec[j].fi.se, +1), j++;
ans += ask(col1, row2);
}
while (j > 0){
j--;
upd(vec[j].fi.fi, vec[j].fi.se, -1);
}
}
return ans;
}
/*
10 10
3 2 2 2 5 1 1 1 1 1
3 1 1 1 2 1 1 1 1 1
6 2 2 2 3 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
*/
