#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){
p += n;
seg[id][p].mn = seg[id][p].mx = val;
while (p > 1){
seg[id][p / 2].mn = min(seg[id][p].mn, seg[id][p ^ 1].mn);
seg[id][p / 2].mx = max(seg[id][p].mx, seg[id][p ^ 1].mx);
p /= 2;
}
}
int get_max(int id, int l, int r){
int res = -1;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1)
res = max(res, seg[id][l++].mx);
if (r&1)
res = max(res, seg[id][--r].mx);
}
return res;
}
int get_min(int id, int l, int r){
int res = 1e9;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1)
res = min(res, seg[id][l++].mn);
if (r&1)
res = min(res, seg[id][--r].mn);
}
return res;
}
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;
int last = -1;
for (int i = 0; i < n; i ++){
if (last + 15 < i){
mnr = get_min(0, 0, i + 1);
mnc = get_min(1, 0, i + 1);
mxr = get_max(0, 0, i + 1);
mxc = get_max(1, 0, i + 1);
}
else{
for (int j = last + 1; j <= i; j ++){
mnr = min(mnr, a[0][i]);
mnc = min(mnc, a[1][i]);
mxr = max(mxr, a[0][i]);
mxc = max(mxc, a[1][i]);
}
}
last = i;
int ele = (mxr - mnr + 1) * (mxc - mnc + 1);
if (ele == (i + 1))
ans++;
else
i = ele - 2;
}
return ans;
}
