#include <bits/stdc++.h>
#include "rect.h"
using ll = long long;
template <class T> using Vec = std::vector<T>;
struct UnionFind {
Vec<int> par;
UnionFind(const int n): par(n, -1) {}
int find(const int x) {
return par[x] < 0 ? x : par[x] = find(par[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (par[x] > par[y]) {
std::swap(x, y);
}
par[x] += par[y];
par[y] = x;
}
};
ll count_rectangles(Vec<Vec<int>> a) {
const int n = (int) a.size();
const int m = (int) a[0].size();
if (n <= 3 or (n <= 700 and m <= 700)) {
Vec<Vec<std::pair<int, int>>> cand(n);
for (int i = 0; i < n; ++i) {
Vec<int> stack;
for (int j = 0; j < m; ++j) {
int max = 0;
while (!stack.empty() and a[i][stack.back()] < a[i][j]) {
if (stack.back() + 1 < j and max < a[i][stack.back()]) {
cand[i].emplace_back(stack.back(), j);
}
max = std::max(max, a[i][stack.back()]);
stack.pop_back();
}
if (!stack.empty() and stack.back() + 1 < j) {
cand[i].emplace_back(stack.back(), j);
}
stack.push_back(j);
}
std::sort(cand[i].begin(), cand[i].end());
}
ll ret = 0;
for (int u = 0; u < n; ++u) {
Vec<int> max(m);
Vec<int> ok(m + 1);
Vec<std::pair<int, int>> pair;
for (int d = u + 2; d < n; ++d) {
for (int j = 0; j < m; ++j) {
max[j] = std::max(max[j], a[d - 1][j]);
ok[j + 1] = ok[j] + (max[j] < std::min(a[u][j], a[d][j]));
}
if (d == u + 2) {
pair = cand[d - 1];
} else {
Vec<std::pair<int, int>> next;
const auto& add = cand[d - 1];
int l = 0, r = 0;
while (l < (int) pair.size() and r < (int) add.size()) {
if (pair[l] < add[r]) {
l += 1;
} else if (add[r] < pair[l]) {
r += 1;
} else {
next.emplace_back(pair[l]);
l += 1;
r += 1;
}
}
pair = std::move(next);
}
for (const auto [l, r]: pair) {
if (ok[r] - ok[l + 1] == r - (l + 1)) {
ret += 1;
}
}
}
}
return ret;
}
else {
UnionFind dsu(n * m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == 0) {
if (i > 0 and a[i - 1][j] == 0) {
dsu.merge((i - 1) * m + j, i * m + j);
}
if (j > 0 and a[i][j - 1] == 0) {
dsu.merge(i * m + (j - 1), i * m + j);
}
}
}
}
Vec<int> u(n * m, n), d(n * m, -1), l(n * m, m), r(n * m, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
const int k = dsu.find(i * m + j);
u[k] = std::min(u[k], i);
d[k] = std::max(d[k], i);
l[k] = std::min(l[k], j);
r[k] = std::max(r[k], j);
}
}
ll ret = 0;
for (int k = 0; k < n * m; ++k) {
if (u[k] == n or u[k] == 0 or d[k] == n - 1 or l[k] == 0 or r[k] == m - 1) {
continue;
}
if ((d[k] - u[k] + 1) * (r[k] - l[k] + 1) == -dsu.par[k]) {
ret += 1;
}
}
return ret;
}
}
