#include "seats.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
constexpr int inf = 1e9;
struct Tree {
struct T {
int mn = inf, mx = -inf;
static T from(int x) { return {x, x}; }
T static combine(T f, T s) { return {min(f.mn, s.mn), max(f.mx, s.mx)}; }
};
vector<T> tree;
void pull(int i) { tree[i] = T::combine(tree[2 * i], tree[2 * i + 1]); }
void init(vector<int> const &base) {
int n = base.size();
tree.resize(4 * n);
_build(1, 0, n - 1, base);
}
void _build(int i, int l, int r, vector<int> const &base) {
if (l == r) {
tree[i] = T::from(base[l]);
return;
}
int m = (l + r) / 2;
_build(2 * i, l, m, base);
_build(2 * i + 1, m + 1, r, base);
pull(i);
}
T get(int i, int l, int r, int lb, int rb) const {
if (r < lb || l > rb) {
return {};
}
if (lb <= l && r <= rb) {
return tree[i];
}
int m = (l + r) / 2;
return T::combine(get(2 * i, l, m, lb, rb), get(2 * i + 1, m + 1, r, lb, rb));
}
void update(int i, int l, int r, int pos, int x) {
if (pos < l || pos > r) {
return;
}
if (l == r) {
tree[i] = T::from(x);
return;
}
int m = (l + r) / 2;
update(2 * i, l, m, pos, x);
update(2 * i + 1, m + 1, r, pos, x);
pull(i);
}
};
vector<int> r, c;
Tree rt, ct;
int n;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H * W;
r = R;
c = C;
rt.init(r);
ct.init(c);
}
int swap_seats(int a, int b) {
swap(r[a], r[b]);
rt.update(1, 0, n - 1, a, r[a]);
rt.update(1, 0, n - 1, b, r[b]);
swap(c[a], c[b]);
ct.update(1, 0, n - 1, a, c[a]);
ct.update(1, 0, n - 1, b, c[b]);
int res = 0;
int i = 0;
while (i < n) {
auto rr = rt.get(1, 0, n - 1, 0, i);
auto cc = ct.get(1, 0, n - 1, 0, i);
int sz = (rr.mx - rr.mn + 1) * (cc.mx - cc.mn + 1);
if (sz == i + 1) {
res++;
++i;
} else {
i = sz - 1;
}
}
return res;
}
