#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
struct ST{
vector<pii> t;
int n;
void init(int ns){
n = ns;
t.resize(4 * n);
}
void upd(int v, int tl, int tr, int& p, int& x){
if (tl == tr){
t[v] = {x, x};
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
if (p <= tm){
upd(vv, tl, tm, p, x);
}
else {
upd(vv + 1, tm + 1, tr, p, x);
}
t[v].ff = min(t[vv].ff, t[vv + 1].ff);
t[v].ss = max(t[vv].ss, t[vv + 1].ss);
}
void upd(int p, int x){
upd(1, 1, n, p, x);
}
int fn1(int v, int tl, int tr, int& x){
if (tl == tr) return tl;
int tm = (tl + tr) / 2, vv = 2 * v;
if (t[vv].ss > x) return fn1(vv, tl, tm, x);
return fn1(vv + 1, tm + 1, tr, x);
}
int find1(int v, int tl, int tr, int& l, int& r, int& x){
if (l > tr || r < tl) return -1;
if (l <= tl && tr <= r){
return (t[v].ss > x) ? fn1(v, tl, tr, x) : -1;
}
int tm = (tl + tr) / 2, vv = 2 * v, j = find1(vv, tl, tm, l, r, x);
return (j == -1) ? (find1(vv + 1, tm + 1, tr, l, r, x)) : j;
}
int find1(int l, int x){
int j = find1(1, 1, n, l, n, x);
return (j == -1) ? (n + 1) : j;
}
int fn2(int v, int tl, int tr, int& x){
if (tl == tr) return tl;
int tm = (tl + tr) / 2, vv = 2 * v;
if (t[vv].ff < x) return fn2(vv, tl, tm, x);
return fn2(vv + 1, tm + 1, tr, x);
}
int find2(int v, int tl, int tr, int& l, int& r, int& x){
if (l > tr || r < tl) return -1;
if (l <= tl && tr <= r){
return (t[v].ff < x) ? fn2(v, tl, tr, x) : -1;
}
int tm = (tl + tr) / 2, vv = 2 * v, j = find2(vv, tl, tm, l, r, x);
return (j == -1) ? (find2(vv + 1, tm + 1, tr, l, r, x)) : j;
}
int find2(int l, int x){
int j = find2(1, 1, n, l, n, x);
return (j == -1) ? (n + 1) : j;
}
};
vector<int> x, y;
int h, w, k;
ST T1, T2;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H; w = W; k = h * w;
x.resize(k + 1);
y.resize(k + 1);
T1.init(k); T2.init(k);
for (int i = 1; i <= k; i++){
x[i] = R[i - 1] + 1;
y[i] = C[i - 1] + 1;
T1.upd(i, x[i]);
T2.upd(i, y[i]);
}
}
int swap_seats(int a, int b){
a++; b++;
T1.upd(a, x[b]);
T1.upd(b, x[a]);
swap(x[a], x[b]);
T2.upd(a, y[b]);
T2.upd(b, y[a]);
swap(y[a], y[b]);
if (h <= 1000 && w <= 1000){
int i = 1, m1 = x[1], m2 = x[1], m3 = y[1], m4 = y[1], out = 0;
vector<int> t(4);
while (true){
if (!t[0]) t[0] = T1.find1(i, m1);
if (!t[1]) t[1] = T1.find2(i, m2);
if (!t[2]) t[2] = T2.find1(i, m3);
if (!t[3]) t[3] = T2.find2(i, m4);
int j = min({t[0], t[1], t[2], t[3]});
int pr = (m1 - m2 + 1) * (m3 - m4 + 1);
out += (i <= pr && pr < j);
if (j > k) break;
if (t[0] == j){
m1 = x[j];
t[0] = 0;
}
if (t[1] == j){
m2 = x[j];
t[1] = 0;
}
if (t[2] == j){
m3 = y[j];
t[2] = 0;
}
if (t[3] == j){
m4 = y[j];
t[3] = 0;
}
i = j;
}
return out;
}
else {
int out = 1, m1 = x[1], m2 = x[1], m3 = y[1], m4 = y[1];
for (int i = 2; i <= k; i++){
m1 = min(m1, x[i]); m2 = max(m2, x[i]);
m3 = min(m3, y[i]); m4 = max(m4, y[i]);
out += ((m2 - m1 + 1) * (m4 - m3 + 1) == i);
}
return out;
}
}
