#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 = 0; i < 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 H = get_linii(a), V = get_linii(b);
for(auto &[x, y] : V) 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;
for(auto [x1, y1] : H) {
for(auto [x2, y2] : V) {
int v = inclus(x1, x2) && inclus(y2, y1);
re += v;
// if(v) {
// printf("(%d %d) (%d %d) | ", x1.first, x1.second, y1.first, y1.second);
// printf("(%d %d) (%d %d)\n", x2.first, x2.second, y2.first, y2.second);
// ++re;
// }
}
}
// for(auto [x, y] : V) {
// printf("(%d %d) (%d %d)\n", x.first, x.second, y.first, y.second);
// }
return re;
}
