#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 vector<ii> inter;
const int len = 2505;
int po[len], mat[len][len], n, m;
inter row_inter[len], col_inter[len];
void print(inter now){
for (int i = 0; i < now.size(); i++)
printf(" (%d, %d)\n", now[i].fi, now[i].se);
printf("\n");
}
inter make_inter(vector<int> vec){
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(stck.back()+1, i-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(i+1, stck.back()-1));
stck.pb(i);
}
sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
inter join(inter &fir, inter &sec){
inter res;
for (int i = 0, j = 0; i < fir.size(); i++){
while (j < sec.size() && sec[j] < fir[i])
j++;
if (j < sec.size() && sec[j] == fir[i])
res.pb(fir[i]);
}
return res;
}
struct{
struct rec{
int ar, br, ac, bc;
rec(int ar_ = len, int br_ = 0, int ac_ = len, int bc_ = 0){
ar = ar_;
br = br_;
ac = ac_;
bc = bc_;
}
void upd(rec other){
ar = min(ar, other.ar);
br = max(br, other.br);
ac = min(ac, other.ac);
bc = max(bc, other.bc);
}
int area(){
return (br-ar+1) * (bc-ac+1);
}
};
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
int vis[len][len];
int dfs(int x, int y, rec &tot){
vis[x][y] = 1;
int cnt = 1;
tot.upd(rec(x, x, y, y));
for (int d = 0; d < 4; d++){
int i = x+dr[d];
int j = y+dc[d];
if (i >= 0 && i < n && j >= 0 && j < m && mat[i][j] == 0 && !vis[i][j])
cnt += dfs(i, j, tot);
}
return cnt;
}
int solve(){
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (!vis[i][j] && mat[i][j] == 0){
rec temp;
int cnt = dfs(i, j, temp);
if (temp.ar > 0 && temp.br < n-1 && temp.ac > 0 && temp.bc < m-1 && temp.area() == cnt)
ans++;
}
return ans;
}
} subtask6;
ll count_rectangles(vector<vector<int> > M) {
n = M.size(), m = M[0].size();
int sub6 = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++){
mat[i][j] = M[i][j];
if (mat[i][j] > 1) sub6 = 0;
}
if (sub6)
return subtask6.solve();
//printf("n = %d, m = %d\n", n, m);
for (int i = 0; i < n; i++){
vector<int> vec;
for (int j = 0; j < m; j++)
vec.pb(mat[i][j]);
row_inter[i] = make_inter(vec);
//printf("row = %d\n", i);
//print(row_inter[i]);
}
for (int j = 0; j < m; j++){
vector<int> vec;
for (int i = 0; i < n; i++)
vec.pb(mat[i][j]);
col_inter[j] = make_inter(vec);
//printf("col = %d\n", j);
//print(col_inter[j]);
}
ll ans = 0;
for (int st_row = 0; st_row < n; st_row++){
inter cur = row_inter[st_row];
for (int j = 0; j < m; j++)
po[j] = 0;
for (int en_row = st_row; en_row < n; en_row++){
vector<int> can(m, 0);
for (int j = 0; j < m; j++){
while (po[j] < col_inter[j].size() && col_inter[j][po[j]] < mp(st_row, en_row))
po[j]++;
if (po[j] < col_inter[j].size() && col_inter[j][po[j]] == mp(st_row, en_row))
can[j] = 1;
}
for (int j = 1; j < m; j++)
can[j] += can[j-1];
if (en_row != st_row)
cur = join(cur, row_inter[en_row]);
// upd ans
for (auto in: cur){
if (can[in.se]-can[in.fi-1] == in.se-in.fi+1)
ans++; //, printf("st = %d, en = %d, in = (%d, %d)\n", st_row, en_row, in.fi, in.se);
}
}
}
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
*/
