#include "seats.h"
//#include "grader.cpp"
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define OK puts("ok");
#define ll long long
using namespace std;
const int N = (int)1e6 + 7;
const int inf = (int)1e9 + 7;
int n;
inline int min(const int &a, const int &b) {
return (a < b) ? a : b;
}
inline int max(const int &a, const int &b) {
return (a < b) ? b : a;
}
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
struct T {
int treemn[2 * N];
int treemx[2 * N];
T () {
}
void build(int v, int l, int r, vector <int> &V) {
if (l == r) {
treemn[v] = treemx[v] = V[l - 1];
return ;
}
int mid = (l + r) >> 1;
build(v + v, l, mid, V);
build(v + v + 1, mid + 1, r, V);
treemn[v] = min(treemn[v + v], treemn[v + v + 1]);
treemx[v] = max(treemx[v + v], treemx[v + v + 1]);
}
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
if (tl == tr) {
treemn[v] = treemx[v] = val;
return ;
}
int mid = (tl + tr) >> 1;
if (pos <= mid) {
upd(pos, val, v + v, tl, mid);
} else {
upd(pos, val, v + v + 1, mid + 1, tr);
}
treemn[v] = min(treemn[v + v], treemn[v + v + 1]);
treemx[v] = max(treemx[v + v], treemx[v + v + 1]);
}
int getmin(int l, int r, int v = 1, int tl = 1, int tr = n) {
if (tl > r || tr < l) return inf;
if (l <= tl && tr <= r) return treemn[v];
int mid = (tl + tr) >> 1;
return min(getmin(l, r, v + v, tl, mid), getmin(l, r, v + v + 1, mid + 1, tr));
}
int getmax(int l, int r, int v = 1, int tl = 1, int tr = n) {
if (tl > r || tr < l) return 0;
if (l <= tl && tr <= r) return treemx[v];
int mid = (tl + tr) >> 1;
return max(getmax(l, r, v + v, tl, mid), getmax(l, r, v + v + 1, mid + 1, tr));
}
};
T tr[2];
int h, w;
int ans;
int r[N], c[N];
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H;
w = W;
n = h * w;
tr[0].build(1, 1, n, R);
tr[1].build(1, 1, n, C);
for (int i = 0; i < n; i++) {
c[i + 1] = C[i];
r[i + 1] = R[i];
}
}
int swap_seats(int a, int b) {
a++; b++;
swap(r[a], r[b]);
swap(c[a], c[b]);
tr[0].upd(a, r[a]);
tr[1].upd(a, c[a]);
tr[0].upd(b, r[b]);
tr[1].upd(b, c[b]);
ans = 0;
ll area;
for (ll i = 1; i <= n; ) {
pair < int, int > tp1, tp2;
tp1 = {tr[0].getmin(1, i), tr[0].getmax(1, i)};
tp2 = {tr[1].getmin(1, i), tr[1].getmax(1, i)};
area = (tp1.sc - tp1.fr + 1) * 1LL * (tp2.sc - tp2.fr + 1);
if (i == area) {
ans++;
i++;
} else {
i = area;
}
}
// cerr << ans << endl;
return ans;
}
