#include "seats.h"
#include <set>
#include <algorithm>
using namespace std;
const int M = 1005;
const int N = 1e6 + 10;
int h, w;
int r[N], c[N];
set<int> sr[N], sc[N];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H, w = W;
for (int i = 0; i < h * w; ++i) {
r[i] = R[i], c[i] = C[i];
}
for (int i = 0; i < h * w; ++i) {
sr[r[i]].insert(i);
sc[c[i]].insert(i);
}
}
int swap_seats(int a, int b) {
sr[r[a]].erase(a);
sc[c[a]].erase(a);
sr[r[b]].erase(b);
sc[c[b]].erase(b);
swap(r[a], r[b]);
swap(c[a], c[b]);
sr[r[a]].insert(a);
sc[c[a]].insert(a);
sr[r[b]].insert(b);
sc[c[b]].insert(b);
vector<pair<int, int>> v;
for (int i = 0; i < h; ++i) {
v.emplace_back(*sr[i].begin(), i + 1);
}
for (int i = 0; i < w; ++i) {
v.emplace_back(*sc[i].begin(), -i - 1);
}
sort(v.begin(), v.end());
int res = 0;
int minr = h - 1, maxr = 0, minc = w - 1, maxc = 0;
for (int i = 0; i < h + w; ++i) {
if (v[i].second > 0) {
minr = min(minr, v[i].second - 1);
maxr = max(maxr, v[i].second - 1);
} else {
minc = min(minc, -v[i].second - 1);
maxc = max(maxc, -v[i].second - 1);
}
if (i == h + w - 1 || v[i].first < v[i + 1].first) {
int s = (maxr - minr + 1) * (maxc - minc + 1);
if (s >= v[i].first + 1 && (i == h + w - 1 || s <= v[i + 1].first)) {
++res;
}
}
}
return res;
}
