#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
vector<pair<ii, ii> > get_linii(vector<vi> &a) {
int n = int(a.size()), m = int(a[0].size());
vector<set<ii> > Perechi(n);
for(int i = 1; i + 1 < n; ++i) {
vector<ii> ord;
for(int j = 0; j < m; ++j)
ord.push_back({a[i][j], j});
sort(ord.rbegin(), ord.rend());
set<int> Poz;
int p2 = 0;
for(int j = 0; j < m; ++j) {
auto [v, p] = ord[j];
while(p2 < m && ord[p2].first == v) {
Poz.insert(ord[p2].second);
++p2;
}
if(1) {
auto it = Poz.lower_bound(p);
++it;
if(it != Poz.end()) {
if(*it > p + 1)
Perechi[i].insert(ii{p, *it});
}
}
if(1) {
auto it = Poz.lower_bound(p);
if(it != Poz.begin()) {
--it;
if(p > *it + 1)
Perechi[i].insert(ii{*it, p});
}
}
}
}
vector<pair<ii, ii> > Re;
for(int i = 0; i < n; ++i) {
for(auto it : Perechi[i]) {
int p = i;
while(p + 1 < n && Perechi[p + 1].count(it)) ++p;
Re.push_back({{i - 1, p + 1}, it});
for(int j = i + 1; j <= p; ++j)
Perechi[j].erase(it);
}
}
return Re;
}
ll count_rectangles(vector<vi> a) {
int n = int(a.size()), m = int(a[0].size());
vector<vi> b(m, vi(n, 0));
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
b[j][i] = a[i][j];
auto V = get_linii(a), H = get_linii(b);
for(auto &[x, y] : H) swap(x, y);
auto inclus = [&](ii a, ii b) {
///b inclus in a
return b.first >= a.first && b.second <= a.second;
};
int re = 0;
vector< vector<vector<ii> > > LinV(n, vector(m, vector<ii>()));
auto LinH = LinV;
for(auto [x, y] : V) {
for(int i = x.first; i <= x.second; ++i) {
LinV[i][y.second].push_back({i - x.first, y.second - y.first});
}
}
for(auto [x, y] : H) {
for(int j = y.first; j <= y.second; ++j) {
LinH[x.second][j].push_back({x.second - x.first, j - y.first});
}
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
for(auto [xh, yh] : LinH[i][j]) {
for(auto [xv, yv] : LinV[i][j]) {
if(xh <= xv & yh >= yv)
++re;
}
}
}
}
return re;
}
