#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
int id(int x, int y) { return x + y * n; }
struct val {
int cnt, x1, y1, x2, y2;
bool used = 0;
val(int x, int y) : cnt(1), x1(x), x2(x), y1(y), y2(y) {};
val() :val(-1, -1) {};
};
val ad(val a, val b) {
a.x1 = min(a.x1, b.x1);
a.x2 = max(a.x2, b.x2);
a.y1 = min(a.y1, b.y1);
a.y2 = max(a.y2, b.y2);
a.cnt += b.cnt;
a.used = 0;
return a;
}
bool is(val a) {
return (a.x2 - a.x1 + 1) * (a.y2 - a.y1 + 1) == a.cnt && !a.used;
}
struct dsu {
vector<int> p;
vector<val> d;
dsu() {
p = vector<int>(n * m, -1);
d = vector<val>(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
d.at(id(i, j)) = val(i, j);
}
}
}
int getp(int v) {
return p.at(v) == -1 ? v : p.at(v) = getp(p.at(v));
}
void merge(int a, int b) {
a = getp(a); b = getp(b);
if (a == b) return;
if (d.at(a).cnt < d.at(b).cnt) swap(a, b);
d.at(a) = ad(d.at(a), d.at(b));
p.at(b) = a;
}
};
bool in_bounds(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
vector<int> dx = { -1, 1, 0, 0 }, dy = { 0, 0, -1, 1 };
const int mx = 7e6 + 5;
vector<pair<int, int>> uwu[mx];
long long count_rectangles(std::vector<std::vector<int>> a) {
n = a.size(); m = a.at(0).size();
dsu ac;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
uwu[a.at(i).at(j)].push_back({ i, j });
}
}
vector<vector<int>> active(n, vector<int>(m, 0));
int res = 0;
for (int i = 0; i < mx; i++) {
for (auto& t : uwu[i]) {
auto [x, y] = t;
active.at(x).at(y) = 1;
for (int j = 0; j < 4; j++) {
int x2 = x + dx.at(j), y2 = y + dy.at(j);
if (!in_bounds(x2, y2) || !active.at(x2).at(y2)) continue;
ac.merge(id(x, y), id(x2, y2));
}
}
for (auto& t : uwu[i]) {
auto [x, y] = t;
int v = ac.getp(id(x, y));
if (is(ac.d.at(v))) {
ac.d.at(v).used = 1; res++;
}
}
}
return res;
}
