#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e6 + 100;
int n, h, w;
vector<int> r, c;
struct Node {
int mxX = -1e7, mnX = 1e7, mxY = -1e7, mnY = 1e7;
Node operator + (Node a) {
return {max(mxX, a.mxX), min(mnX, a.mnX), max(mxY, a.mxY), min(mnY, a.mnY)};
}
} null;
struct SGT {
vector<Node> sgt;
SGT(int sz) {
sgt.resize(4 * sz);
}
void update(int k, int l, int r, int i, int x, int y) {
if (l > i || r < i) return;
if (l == r) {
sgt[k] = {x, x, y, y};
return;
}
int mid = (l + r) / 2;
update(k * 2, l, mid, i, x, y);
update(k * 2 + 1, mid + 1, r, i, x, y);
sgt[k] = sgt[k * 2] + sgt[k * 2 + 1];
}
Node get(int k, int l, int r, int i, int j) {
if (l > j || r < i) return null;
if (i <= l && r <= j) return sgt[k];
int mid = (l + r) / 2 ;
return get(k * 2, l, mid, i, j) + get(k * 2 + 1, mid + 1, r, i, j);
}
} sgt(mxn);
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H, w = W, r = R, c = C;
n = h * w;
for (int i = 0; i < n; i++) sgt.update(1, 0, n - 1, i, r[i], c[i]);
}
int swap_seats(int a, int b) {
swap(r[a], r[b]);
swap(c[a], c[b]);
sgt.update(1, 0, n - 1, a, r[a], c[a]);
sgt.update(1, 0, n - 1, b, r[b], c[b]);
int ind = 0, ans = 0;
while (ind < n) {
Node get = sgt.get(1, 0, n - 1, 0, ind);
int area = (get.mxX - get.mnX + 1) * (get.mxY - get.mnY + 1);
if (area == ind + 1) ans++;
ind = max(ind + 1, area - 1);
}
return ans;
}
