#include <iostream>
#include <vector>
using namespace std;
const int N = (1<<20) + 1;
int Mnr[N<<1], Mxr[N<<1], Mnc[N<<1], Mxc[N<<1];
vector<int> R, C;
int n, m;
void upd(int i, int r, int c, int cur = 1, int st = 1, int en = N){
if (i >= en or i < st)
return;
if (en - st == 1){
Mnr[cur] = Mxr[cur] = r, Mnc[cur] = Mxc[cur] = c;
return;
}
int lc = cur << 1, rc = lc | 1, mid = (st + en) >> 1;
upd(i, r, c, lc, st, mid);
upd(i, r, c, rc, mid, en);
Mnr[cur] = min(Mnr[lc], Mnr[rc]);
Mxr[cur] = max(Mxr[lc], Mxr[rc]);
Mnc[cur] = min(Mnc[lc], Mnc[rc]);
Mxc[cur] = max(Mxc[lc], Mxc[rc]);
}
int x1, y1, x2, y2;
void get(int l, int r, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return;
if (l <= st and r >= en){
x1 = min(x1, Mnr[cur]);
x2 = max(x2, Mxr[cur]);
y1 = min(y1, Mnc[cur]);
y2 = max(y2, Mxc[cur]);
return;
}
int lc = cur << 1, rc = lc | 1, mid = (st + en) >> 1;
get(l, r, lc, st, mid);
get(l, r, rc, mid, en);
}
void give_initial_chart(int r, int c, vector<int> x, vector<int> y){
n = r, m = c;
R = x, C = y;
for (int i=0;i<n*m;i++)
upd(i+1, R[i], C[i]);
}
int swap_seats(int a, int b){
swap(R[a], R[b]);
swap(C[a], C[b]);
int Ans = 0;
if (n * m <= 10000){
x1 = y1 = 1e9, x2 = y2 = 0;
for (int i=0;i<n * m;i++){
x1 = min(x1, R[i]);
y1 = min(y1, C[i]);
x2 = max(x2, R[i]);
y2 = max(y2, C[i]);
if ((x2 - x1 + 1) * (y2 - y1 + 1) == i + 1)
Ans++;
}
}
else{
upd(a + 1, R[a], C[a]);
upd(b + 1, R[b], C[b]);
for (int i=1;i<=n * m;){
x1 = y1 = 1e9, x2 = y2 = 0;
get(1, i+1);
if ((x2 - x1 + 1) * (y2 - y1 + 1) == i)
Ans++, i++;
else
i = (x2 - x1 + 1) * (y2 - y1 + 1);
}
}
return Ans;
}
