#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
const int MN = 2500;
struct DSU {
vi e, mi, ma;
DSU(int n) : e(n, -1), mi(n), ma(n) {
iota(mi.begin(), mi.end(), 0);
iota(ma.begin(), ma.end(), 0);
}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
void join(int u, int v) {
u = repr(u); v = repr(v);
if(u == v) return;
if(e[u] >= e[v]) swap(u, v);
e[u] += e[v];
e[v] = u;
mi[u] = min(mi[u], mi[v]);
ma[u] = max(ma[u], ma[v]);
}
ii get_seg(int u) {
u = repr(u);
return ii{mi[u], ma[u]};
}
};
vector<ii> Perechi[MN][MN];
vector<pair<ii, ii> > get_linii(vector<vi> &a) {
int n = int(a.size()), m = int(a[0].size());
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.begin(), ord.end());
DSU Poz(m);
vector<bool> on(m, false);
int p2 = 0;
for(int j = 0; j < m; ++j) {
auto [v, p] = ord[j];
while(p2 < m && ord[p2].first < v) {
int u = ord[p2].second;
on[u] = true;
if(u && on[u - 1]) Poz.join(u, u - 1);
if(u + 1 < m && on[u + 1]) Poz.join(u, u + 1);
++p2;
}
if(p && on[p - 1]) {
auto [mi, ma] = Poz.get_seg(p - 1);
if(mi)
Perechi[i][p].push_back({mi - 1, p});
}
if(p + 1 < n && on[p + 1]) {
auto [mi, ma] = Poz.get_seg(p + 1);
if(ma + 1 < n) {
Perechi[i][p].push_back({p, ma + 1});
//Perechi[i].insert(p * m + ma + 1);
}
}
}
}
vector<pair<ii, ii> > Re;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
for(auto [st, dr] : Perechi[i][j]) {
int p = i;
int ok = 1;
if(!i) {
for(auto [s1, d1]: Perechi[p - 1][st])
if(s1 == st && d1 == dr) ok = 0;
for(auto [s1, d1]: Perechi[p - 1][dr])
if(s1 == st && d1 == dr) ok = 0;
}
if(!ok) continue; // nu suntem primii
while(p + 1 < n) {
int ok = 0;
for(auto [s1, d1]: Perechi[p][st])
if(s1 == st && d1 == dr) ok = 1;
for(auto [s1, d1]: Perechi[p][dr])
if(s1 == st && d1 == dr) ok = 1;
if(ok)
++p;
else break;
}
Re.push_back({{i - 1, p + 1}, {st, dr}});
}
}
}
return Re;
}
namespace AIB {
const int MN = 2501;
int V[MN];
void update(int p, int v) {
++p;
while(p < MN) {
V[p] += v;
p += p & -p;
}
}
int query(int p) {
++p;
if(p < 0) return 0;
int re = 0;
while(p) {
re += V[p];
p -= p & -p;
}
return re;
}
};
vector<ii> LinV[MN][MN];
vector<ii> LinH[MN][MN];
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);
return 0;
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;
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) {
int l1 = (int)LinH[i][j].size(), l2 = (int)LinV[i][j].size();
sort(LinH[i][j].begin(), LinH[i][j].end());
sort(LinV[i][j].begin(), LinV[i][j].end());
int p = 0;
for(auto [xv, yv] : LinV[i][j]) {
while(p < l1 && LinH[i][j][p].first <= xv) {
AIB::update(m - LinH[i][j][p].second - 1, 1);
++p;
}
re += AIB::query(m - yv - 1);
}
while(p)
AIB::update(m - LinH[i][j][--p].second - 1, -1);
}
}
return re;
}
