#include "seats.h"
#include <bits/stdc++.h>
template <class M>
class SegmentTree {
using T = typename M::T;
int n, size;
std::vector<T> data;
void update(int i) {
data[i] = M::op(data[2 * i], data[2 * i + 1]);
}
public:
SegmentTree() {}
SegmentTree(const std::vector<T> &vec) {
n = (int)vec.size();
size = 1;
while (size < n) {
size *= 2;
}
data.assign(2 * size, M::e());
std::copy(vec.begin(), vec.end(), data.begin() + size);
for (int i = size - 1; i >= 1; --i) update(i);
}
void set(int i, const T &v) {
i += size;
data[i] = v;
while (i != 1) {
i /= 2;
update(i);
}
}
T fold(int l, int r) {
T pl = M::e(), pr = M::e();
for (l += size, r += size; l < r; l /= 2, r /= 2) {
if (l & 1) pl = M::op(pl, data[l++]);
if (r & 1) pr = M::op(data[--r], pr);
}
return M::op(pl, pr);
}
};
constexpr int inf = 1 << 30;
struct MonoidMinMax {
using T = std::pair<int, int>;
static T op(const T &a, const T &b) {
return {std::min(a.first, b.first), std::max(a.second, b.second)};
}
static T e() {
return {inf, -1};
}
};
int H, W;
std::vector<int> R, C;
SegmentTree<MonoidMinMax> rowSeg, colSeg;
std::vector<std::set<int>> rowIds, colIds;
std::vector<std::pair<int, bool>> firstIds;
void give_initial_chart(int h, int w, std::vector<int> r, std::vector<int> c) {
H = h;
W = w;
R = r;
C = c;
if (H > W) {
std::swap(H, W);
std::swap(R, C);
}
std::vector<std::pair<int, int>> rInit(H * W), cInit(H * W);
for (int i = 0; i < H * W; ++i) {
rInit[i] = {R[i], R[i]};
cInit[i] = {C[i], C[i]};
}
rowSeg = SegmentTree<MonoidMinMax>(rInit);
colSeg = SegmentTree<MonoidMinMax>(cInit);
rowIds.resize(H);
colIds.resize(W);
for (int i = 0; i < H * W; ++i) {
if (colIds[C[i]].empty()) {
firstIds.push_back({i, false});
}
colIds[C[i]].insert(i);
if (rowIds[R[i]].empty()) {
firstIds.push_back({i, true});
}
rowIds[R[i]].insert(i);
}
}
void updRow(int i, int v, bool b) {
if (not rowIds[i].empty()) {
int mi = *rowIds[i].begin();
auto itr = std::find(firstIds.begin(), firstIds.end(), std::make_pair(mi, true));
firstIds.erase(itr);
}
if (b) rowIds[i].insert(v);
else rowIds[i].erase(v);
if (rowIds[i].empty()) return;
int mi = *rowIds[i].begin();
auto itr = std::lower_bound(firstIds.begin(), firstIds.end(), std::make_pair(mi, true));
firstIds.insert(itr, {mi, true});
}
void updCol(int i, int v, bool b) {
if (not colIds[i].empty()) {
int mi = *colIds[i].begin();
auto itr = std::find(firstIds.begin(), firstIds.end(), std::make_pair(mi, false));
firstIds.erase(itr);
}
if (b) colIds[i].insert(v);
else colIds[i].erase(v);
if (colIds[i].empty()) return;
int mi = *colIds[i].begin();
auto itr = std::lower_bound(firstIds.begin(), firstIds.end(), std::make_pair(mi, false));
firstIds.insert(itr, {mi, false});
}
int swap_seats(int a, int b) {
// upd
updRow(R[a], a, false);
updCol(C[a], a, false);
updRow(R[b], b, false);
updCol(C[b], b, false);
updRow(R[a], b, true);
updCol(C[a], b, true);
updRow(R[b], a, true);
updCol(C[b], a, true);
rowSeg.set(a, std::make_pair(R[b], R[b]));
rowSeg.set(b, std::make_pair(R[a], R[a]));
colSeg.set(a, std::make_pair(C[b], C[b]));
colSeg.set(b, std::make_pair(C[a], C[a]));
std::swap(R[a], R[b]);
std::swap(C[a], C[b]);
// calc
int answer = 0;
int last = 0;
for (const auto [i, b] : firstIds) {
// at i - 1
if (last == i) {
continue;
}
const auto x = rowSeg.fold(0, i), y = colSeg.fold(0, i);
if ((x.second - x.first + 1) * (y.second - y.first + 1) == i) {
++answer;
}
last = i;
}
++answer;
return answer;
}
