#include <bits/stdc++.h>
#include "rect.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
using namespace std;
using vi = vector<int>;
using i4 = array<int, 4>;
using vi4 = vector<i4>;
void extract(int n, int m, vector<vi> &V, vi4 &V1) {
vector<stack<int> > lin(m);
for(int j = 0; j < m; ++j)
lin[j].push(0);
set<int> Cur;
for(int i = 1; i < n; ++i) {
vector<pair<int, int> > Ult, UrmU; /// perechi (linie, j din trecut)
for(int j = 0; j < m; ++j) {
Cur.clear();
int uv = V[i][j];
while(!lin[j].empty() && V[i][j] > V[lin[j].top()][j]) {
if(V[lin[j].top()][j] != uv) {
Cur.insert(lin[j].top());
uv = V[lin[j].top()][j];
}
lin[j].pop();
}
if(!lin[j].empty()) {
if(V[lin[j].top()][j] != uv) { // desc
Cur.insert(lin[j].top());
uv = V[lin[j].top()][j];
}
}
lin[j].push(i);
UrmU.clear();
for(auto [l, jv] : Ult) {
if(Cur.count(l)) {
UrmU.push_back({l, jv});
Cur.erase(l);
} else {
if(abs(l - i) > 1 && j - 1 - jv >= 0)
V1.push_back(i4{l, i, jv, j - 1});
}
}
swap(Ult, UrmU);
for(auto vc : Cur)
Ult.push_back({vc, j});
}
for(auto [l, jv] : Ult) {
if(abs(l - i) > 1 && m - 1 - jv >= 0)
V1.push_back(i4{l, i, jv, m - 1});
}
}
}
struct CEVA {
int MAX_V = 14000002;
int CMAGIC = 7000001;
vector<tuple<int, int, int> > VQ;
vector<int> V;
void fake_update(int v1, int v2, int v3) {
v1 += CMAGIC;
v2 += CMAGIC;
v3 += CMAGIC;
while(v1 < MAX_V) {
int a = v2;
while(a < MAX_V) {
int b = v3;
while(b < MAX_V) {
VQ.push_back({v1, a, b});
b += b & -b;
}
a += a & -a;
}
v1 += v1 & -v1;
}
}
void init() {
sort(VQ.begin(), VQ.end());
VQ.resize(unique(VQ.begin(), VQ.end()) - VQ.begin());
V.assign(VQ.size(), 0);
}
int id(tuple<int, int, int> q) {
int p = lower_bound(VQ.begin(), VQ.end(),
q) - VQ.begin();
if(VQ[p] != q) p = -1;
return p;
}
void update(int v1, int v2, int v3) {
v1 += CMAGIC;
v2 += CMAGIC;
v3 += CMAGIC;
while(v1 < MAX_V) {
int a = v2;
while(a < MAX_V) {
int b = v3;
while(b < MAX_V) {
V[id({v1, a, b})] += 1;
b += b & -b;
}
a += a & -a;
}
v1 += v1 & -v1;
}
}
int query(int v1, int v2, int v3) {
v1 += CMAGIC;
v2 += CMAGIC;
v3 += CMAGIC;
int re = 0;
while(v1) {
int a = v2;
while(a) {
int b = v3;
while(b) {
int p = id({v1, a, b});
if(p != -1) re += V[p];
b -= b & -b;
}
a -= a & -a;
}
v1 -= v1 & -v1;
}
return re;
}
};
long long count_rectangles(std::vector<std::vector<int> > V) {
int n = V.size(), m = V[0].size();
vector<vi> VT(m, vi(n, 0));
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
VT[j][i] = V[i][j];
vi4 V1, V2;
extract(n, m, V, V1);
extract(m, n, VT, V2);
for(auto &it : V2) {
swap(it[0], it[2]);
swap(it[1], it[3]);
}
for(auto &it : V1) {
++it[0];
--it[1];
}
for(auto &it : V2) {
++it[2];
--it[3];
}
for(auto &it : V1) {
it[0] *= -1;
it[3] *= -1;
}
for(auto &it : V2) {
it[0] *= -1;
it[3] *= -1;
}
using i3 = array<int, 3>;
sort(V1.begin(), V1.end(), [&](auto a, auto b) {
return a[0] < b[0];
});
sort(V2.begin(), V2.end(), [&](auto a, auto b) {
return a[0] < b[0];
});
int p = 0;
vector<i3> W;
long long re = 0;
for(auto it : V2) {
while(p < V1.size() && V1[p][0] <= it[0]) {
W.push_back(i3{V1[p][1], V1[p][2], V1[p][3]});
++p;
}
for(auto it2 : W) {
int ok = 1;
for(int i = 0; i < 3; ++i)
ok &= it[i + 1] >= it2[i];
re += ok;
}
}
return re;
}
