#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int H, W;
vector<int> R, C;
int LO = 0;
int HI = 0;
struct SegmentTree {
vector<int> mn, mx;
SegmentTree(const vector<int> &arr) {
mn.resize(4 * arr.size());
mx.resize(4 * arr.size());
build(LO, HI - 1, 0, arr);
}
void build(int l, int r, int node, const vector<int>&arr) {
if (l == r) {
mn[node] = arr[l];
mx[node] = arr[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, (node << 1) + 1, arr);
build(mid + 1, r, (node << 1) + 2, arr);
mn[node] = min(mn[(node << 1) + 1], mn[(node << 1) + 2]);
mx[node] = max(mx[(node << 1) + 1], mx[(node << 1) + 2]);
}
void modify(int l, int r, int node, int delta, int where) {
if (l == r) {
mn[node] = delta;
mx[node] = delta;
return;
}
int mid = (l + r) >> 1;
if (where <= mid) modify(l, mid, (node << 1) + 1, delta, where);
if (where >= mid + 1) modify(mid + 1, r, (node << 1) + 2, delta, where);
mn[node] = min(mn[(node << 1) + 1], mn[(node << 1) + 2]);
mx[node] = max(mx[(node << 1) + 1], mx[(node << 1) + 2]);
}
pair<int, int> query(int ql, int qr, int l, int r, int node) {
if (l >= ql && r <= qr) {
return make_pair(mn[node], mx[node]);
}
int mid = (l + r) >> 1;
pair<int, int> esq = {INF, -INF};
if (ql <= mid) {
esq = query(ql, qr, l, mid, (node << 1) + 1);
}
pair<int, int> dir = {INF, -INF};
if (qr >= mid + 1) {
dir = query(ql, qr, mid + 1, r, (node << 1) + 2);
}
return make_pair( (esq.first < dir.first ? esq.first : dir.first) , (esq.second > dir.second ? esq.second : dir.second) );
}
};
SegmentTree *rows_tree;
SegmentTree *cols_tree;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
::H = H; ::W = W;
::R = R; ::C = C;
::HI = H * W;
rows_tree = new SegmentTree(R);
cols_tree = new SegmentTree(C);
}
int swap_seats(int a, int b) {
swap(R[a], R[b]);
swap(C[a], C[b]);
rows_tree -> modify(LO, HI - 1, 0, R[a], a);
cols_tree -> modify(LO, HI - 1, 0, C[a], a);
rows_tree -> modify(LO, HI - 1, 0, R[b], b);
cols_tree -> modify(LO, HI - 1, 0, C[b], b);
int res = 0;
int current_idx = 0;
while(current_idx < HI) {
pair<int, int> A = rows_tree -> query(0, current_idx, LO, HI - 1, 0);
pair<int, int> B = cols_tree -> query(0, current_idx, LO, HI - 1, 0);
int score = (A.second - A.first + 1) * (B.second - B.first + 1);
if (current_idx + 1 == score) {
++res;
++current_idx;
} else {
current_idx = score - 1;
}
}
return res;
}
