#include <bits/stdc++.h>
#include "seats.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
#define md ((l + r) >> 1)
const int N = 1'000'005;
struct node {
int mn, mx;
node() {
mn = 1e9;
mx = -1e9;
}
friend node operator+(const node &l, const node &r) {
node ret;
ret.mn = min(l.mn, r.mn);
ret.mx = max(l.mx, r.mx);
return ret;
}
};
struct segtree {
node seg[1 << 21];
vector<int> a;
void build(int i, int l, int r) {
if (l == r) {
seg[i].mn = seg[i].mx = a[l];
return;
}
build(i << 1, l, md);
build(i << 1 | 1, md + 1, r);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
node get(int i, int l, int r, int s, int e) {
if (s <= l && r <= e) {
return seg[i];
}
if (r < s || e < l) {
return node();
}
return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
}
void upd(int i, int l, int r, int x, int v) {
if (l == r) {
seg[i].mn = seg[i].mx = v;
return;
}
if (x <= md) {
upd(i << 1, l, md, x, v);
} else {
upd(i << 1 | 1, md + 1, r, x, v);
}
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
} segr, segc;
int n, m;
vector<int> r, c;
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
n = _n, m = _m;
r = _r, c = _c;
segr.a = r;
segc.a = c;
segr.build(1, 0, n * m - 1);
segc.build(1, 0, n * m - 1);
}
int swap_seats(int x, int y) {
if (x > y) swap(x, y);
swap(r[x], r[y]);
segr.upd(1, 0, n * m - 1, x, r[x]);
segr.upd(1, 0, n * m - 1, y, r[y]);
swap(c[x], c[y]);
segc.upd(1, 0, n * m - 1, x, c[x]);
segc.upd(1, 0, n * m - 1, y, c[y]);
int i = 0, cnt = 0;
while (i < n * m) {
node vr = segr.get(1, 0, n * m - 1, 0, i);
node vc = segc.get(1, 0, n * m - 1, 0, i);
int val = (vr.mx - vr.mn + 1) * (vc.mx - vc.mn + 1);
if (val == i + 1) {
cnt++;
i++;
} else {
i = val - 1;
}
}
return cnt;
}
