#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2")
using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
const int MN = 2500;
static int encode(int x, int y) { return x * MN + y; }
static ii decode(int v) { return {v / MN, v % MN}; }
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]};
}
};
vi LinV[MN][MN];
vi LinH[MN][MN];
static vector<pair<ii, ii> > get_linii(vector<vi> &a, vi Perechi[][MN]) {
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) Perechi[i][j].clear();
for(int j = 0; j < m; ++j) Perechi[i][j].reserve(2);
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(encode(mi - 1, p));
}
if(p + 1 < m && on[p + 1]) {
auto [mi, ma] = Poz.get_seg(p + 1);
if(ma + 1 < m) {
Perechi[i][p].push_back(encode(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 it0: Perechi[i][j]) {
auto [st, dr] = decode(it0);
int p = i;
int ok = 1;
if(i) {
for(auto it : Perechi[p - 1][st]) {
auto [s1, d1] = decode(it);
if(s1 == st && d1 == dr) ok = 0;
}
for(auto it : Perechi[p - 1][dr]) {
auto [s1, d1] = decode(it);
if(s1 == st && d1 == dr) ok = 0;
}
}
if(!ok) continue; // nu suntem primii
while(p + 1 < n) {
int ok = 0;
for(auto it : Perechi[p + 1][st]) {
auto [s1, d1] = decode(it);
if(s1 == st && d1 == dr) ok = 1;
}
for(auto it : Perechi[p + 1][dr]) {
auto [s1, d1] = decode(it);
if(s1 == st && d1 == dr) ok = 1;
}
if(ok)
++p;
else break;
}
Re.push_back({{i - 1, p + 1}, {st, dr}});
}
}
}
sort(Re.begin(), Re.end());
Re.resize(unique(Re.begin(), Re.end()) - Re.begin());
return Re;
}
namespace AIB {
const int MM = MN + 1;
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;
}
};
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, LinH);
for(auto [x, y] : V) {
for(int i = x.first; i <= x.second; ++i) {
LinV[i][y.second].push_back(encode(i - x.first, y.second - y.first));
}
}
auto H = get_linii(b, LinH);
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
LinH[i][j].clear();
for(auto [x, y] : H) {
swap(x, y);
for(int j = y.first; j <= y.second; ++j) {
LinH[x.second][j].push_back(encode(x.second - x.first, j - y.first));
}
}
ll re = 0;
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 it : LinV[i][j]) {
auto [xv, yv] = decode(it);
while(p < l1 && decode(LinH[i][j][p]).first <= xv) {
AIB::update(m - decode(LinH[i][j][p]).second - 1, 1);
++p;
}
re += AIB::query(m - yv - 1);
}
while(p)
AIB::update(m - decode(LinH[i][j][--p]).second - 1, -1);
}
}
return re;
}
