#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
#define arr3 array<int, 3>
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);
}
vector<arr3> all;
void dec(int v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
all.pb({v, tl, tr});
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
dec(vv, tl, tm, l, r);
dec(vv + 1, tm + 1, tr, l, r);
}
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 l, int x){
all.clear();
dec(1, 1, n, l, n);
for (auto [v, tl, tr]: all){
if (t[v].ss > x){
return fn1(v, tl, tr, x);
}
}
return n + 1;
}
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 l, int x){
all.clear();
dec(1, 1, n, l, n);
for (auto [v, tl, tr]: all){
if (t[v].ff < x){
return fn2(v, tl, tr, x);
}
}
return n + 1;
}
};
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;
while (true){
int j1 = T1.find1(i, m1), j2 = T1.find2(i, m2), j3 = T2.find1(i, m3), j4 = T2.find2(i, m4), j = min({j1, j2, j3, j4});
int pr = (m1 - m2 + 1) * (m3 - m4 + 1);
out += (i <= pr && pr < j);
if (j > k) break;
if (j1 == j) m1 = x[j];
if (j2 == j) m2 = x[j];
if (j3 == j) m3 = y[j];
if (j4 == j) m4 = y[j];
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;
}
}
