#include "rect.h"
#include <algorithm>
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2500 * 2500;
int id[MAXN];
int sz[MAXN];
int minLig[MAXN], maxLig[MAXN], minCol[MAXN], maxCol[MAXN];
bool activated[2500][2500];
int DX[] = {-1, 1, 0, 0};
int DY[] = {0, 0, -1, 1};
int nbLig, nbCol;
set<tuple<int, int, int, int>> rectangles, curRectangles;
int find(int i) {
if (id[i] == i)
return i;
return id[i] = find(id[i]);
}
bool estRectangle(int cc) {
assert(id[cc] == cc);
return minLig[cc] > 0 and maxLig[cc] < nbLig - 1 and minCol[cc] > 0 and
maxCol[cc] < nbCol - 1 and
sz[cc] ==
(1 + maxCol[cc] - minCol[cc]) * (maxLig[cc] - minLig[cc] + 1);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b)
return;
if (sz[a] < sz[b])
swap(a, b);
if (estRectangle(a)) {
curRectangles.erase({minLig[a], maxLig[a], minCol[a], maxCol[a]});
}
if (estRectangle(b)) {
curRectangles.erase({minLig[b], maxLig[b], minCol[b], maxCol[b]});
}
id[b] = a;
sz[a] += sz[b];
minLig[a] = min(minLig[a], minLig[b]);
maxLig[a] = max(maxLig[a], maxLig[b]);
minCol[a] = min(minCol[a], minCol[b]);
maxCol[a] = max(maxCol[a], maxCol[b]);
if (estRectangle(a)) {
curRectangles.insert({minLig[a], maxLig[a], minCol[a], maxCol[a]});
}
}
int hashCoord(int iLig, int iCol) { return iLig * nbCol + iCol; }
void active(int iLig, int iCol) {
int hsh = hashCoord(iLig, iCol);
id[hsh] = hsh;
sz[hsh] = 1;
minLig[hsh] = maxLig[hsh] = iLig;
minCol[hsh] = maxCol[hsh] = iCol;
if (estRectangle(hsh))
curRectangles.insert({iLig, iLig, iCol, iCol});
}
int count_rectangles(vector<vector<signed>> a) {
vector<int> vals;
nbLig = a.size(), nbCol = a[0].size();
for (int iLig = 0; iLig < nbLig; ++iLig)
for (int iCol = 0; iCol < nbCol; ++iCol)
vals.push_back(a[iLig][iCol]);
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
for (int iLig = 0; iLig < nbLig; ++iLig)
for (int iCol = 0; iCol < nbCol; ++iCol)
a[iLig][iCol] =
lower_bound(vals.begin(), vals.end(), a[iLig][iCol]) - vals.begin();
for (int iLig = 0; iLig < nbLig; ++iLig)
for (int iCol = 0; iCol < nbCol; ++iCol)
cout << a[iLig][iCol] << " \n"[iCol == nbCol - 1];
int nbVal = vals.size();
vector<vector<pair<int, int>>> withVal(nbVal);
for (int iLig = 0; iLig < nbLig; ++iLig)
for (int iCol = 0; iCol < nbCol; ++iCol)
withVal[a[iLig][iCol]].emplace_back(iLig, iCol);
for (int val = 0; val < nbVal; ++val) {
for (auto [iLig, iCol] : withVal[val]) {
active(iLig, iCol);
activated[iLig][iCol] = true;
}
for (auto [iLig, iCol] : withVal[val]) {
for (int d = 0; d < 4; ++d) {
int lig = iLig + DX[d];
int col = iCol + DY[d];
if (lig < 0 or col < 0 or lig >= nbLig or col >= nbCol or
!activated[lig][col])
continue;
merge(hashCoord(iLig, iCol), hashCoord(lig, col));
}
}
// cout << val << ' ' << curRectangles.size() << endl;
for (auto v : curRectangles)
rectangles.insert(v);
}
return rectangles.size();
;
}
