#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2500;
const int MAX_CELLS = MAX_N * MAX_N;
int dl[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
bool active[MAX_CELLS];
bool frecv[MAX_CELLS];
int parent[MAX_CELLS];
int bad[MAX_CELLS];
int sizee[MAX_CELLS];
int minL[MAX_CELLS];
int minC[MAX_CELLS];
int maxC[MAX_CELLS];
int maxL[MAX_CELLS];
int findParent(int x) {
if (parent[x] != x)
parent[x] = findParent(parent[x]);
return parent[x];
}
void connect(int x, int y) {
x = findParent(x);
y = findParent(y);
if (x == y)
return;
sizee[x] += sizee[y];
bad[x] += bad[y];
minL[x] = min(minL[x], minL[y]);
maxL[x] = max(maxL[x], maxL[y]);
minC[x] = min(minC[x], minC[y]);
maxC[x] = max(maxC[x], maxC[y]);
}
bool check(int p) {
if (bad[p])
return false;
int area = (maxL[p] - minL[p] + 1) * (maxC[p] - minC[p] + 1);
return (sizee[p] == area);
}
long long count_rectangles(vector<vector<int> > a) {
int n = a.size(), m = a[0].size();
vector<pair<int, pair<int, int>>> sortedCells;
for (int l = 0; l < n; l++) {
for (int c = 0; c < m; c++)
sortedCells.push_back({a[l][c], {l, c}});
}
sort(sortedCells.begin(), sortedCells.end());
int ans = 0;
for (int l = 0; l < n; l++) {
for (int c = 0; c < m; c++) {
int id = l * m + c;
sizee[id] = 1;
parent[id] = id;
minL[id] = maxL[id] = l;
minC[id] = maxC[id] = c;
bad[id] = (l == 0 || c == 0 || l == n - 1 || c == m - 1);
//printf("%d ", a[l][c]);
}
//printf("\n");
}
int ind1 = 0;
while (ind1 < n * m) {
int ind2 = ind1;
int val = a[sortedCells[ind1].second.first][sortedCells[ind1].second.second];
while (ind2 < n * m && a[sortedCells[ind2].second.first][sortedCells[ind2].second.second] == val)
ind2++;
for (int i = ind1; i < ind2; i++) {
int l = sortedCells[i].second.first;
int c = sortedCells[i].second.second;
int id = l * m + c;
for (int d = 0; d < 4; d++) {
int newL = l + dl[d];
int newC = c + dc[d];
int newId = newL * m + newC;
if (active[newId])
connect(id, newId);
}
active[id] = true;
}
for (int i = ind1; i < ind2; i++) {
int l = sortedCells[i].second.first;
int c = sortedCells[i].second.second;
int id = l * m + c;
int p = findParent(id);
if (frecv[p])
continue;
frecv[p] = 1;
if (check(p))
ans++;
// if (check(p))
// printf("%d %d %d\n", l, c, a[l][c]);
}
for (int i = ind1; i < ind2; i++) {
int l = sortedCells[i].second.first;
int c = sortedCells[i].second.second;
int id = l * m + c;
int p = findParent(id);
frecv[p] = 0;
}
ind1 = ind2;
}
return ans;
}
