#include <bits/stdc++.h>
#include "seats.h"
// #include "grader.cpp"
using namespace std;
const int N = 1e6 + 10;
int n, h, w;
vector<int> a[2];
struct node{
int mn, mx;
} seg[2][4 * N];
void modify(int id, int p, int val, int v = 1, int s = 0, int e = n){
if (e - s == 1){
seg[id][v].mn = seg[id][v].mx = val;
return ;
}
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
if (p < mid) modify(id, p, val, lc, s, mid);
else modify(id, p, val, rc, mid, e);
seg[id][v].mn = min(seg[id][lc].mn, seg[id][rc].mn);
seg[id][v].mx = max(seg[id][lc].mx, seg[id][rc].mx);
}
int get_max(int id, int l, int r, int v = 1, int s = 0, int e = n){
if (e <= l || r <= s) return -1;
if (l <= s && e <= r) return seg[id][v].mx;
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
return max(get_max(id, l, r, lc, s, mid), get_max(id, l, r, rc, mid, e));
}
int get_min(int id, int l, int r, int v = 1, int s = 0, int e = n){
if (e <= l || r <= s) return 1e9;
if (l <= s && e <= r) return seg[id][v].mn;
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
return min(get_min(id, l, r, lc, s, mid), get_min(id, l, r, rc, mid, e));
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H, w = W, a[0] = R, a[1] = C;
n = h * w;
for (int id = 0; id < 2; id ++)
for (int i = 0; i < n; i ++)
modify(id, i, a[id][i]);
}
int swap_seats(int x, int y){
for (int id = 0; id < 2; id ++){
swap(a[id][x], a[id][y]);
modify(id, x, a[id][x]);
modify(id, y, a[id][y]);
}
int ans = 0;
int mnr = 1e9, mnc = 1e9, mxr = -1, mxc = -1;
for (int i = 0; i < n; i ++){
mnr = min(mnr, get_min(0, 0, i + 1));
mnc = min(mnc, get_min(1, 0, i + 1));
mxr = max(mxr, get_max(0, 0, i + 1));
mxc = max(mxc, get_max(1, 0, i + 1));
int ele = (mxr - mnr + 1) * (mxc - mnc + 1);
if (ele == (i + 1))
ans++;
else
i = ele - 2;
}
return ans;
}
