#include <bits/stdc++.h>
#include "seats.h"
template <class T> using Vec = std::vector<T>;
namespace {
int H, W;
Vec<int> R, C;
};
void give_initial_chart(int h, int w, Vec<int> r, Vec<int> c) {
H = h, W = w;
R = r, C = c;
}
int swap_seats(int a, int b) {
if (H + W <= 2000) {
std::swap(C[a], C[b]);
std::swap(R[a], R[b]);
int l = C[0], r = C[0], u = R[0], d = R[0];
int ret = 0, cur = 0;
while (cur < H * W) {
l = std::min(l, C[cur]);
r = std::max(r, C[cur]);
u = std::min(u, R[cur]);
d = std::max(d, R[cur]);
if ((r - l + 1) * (d - u + 1) == cur + 1) {
ret += 1;
cur += 1;
} else {
cur = (r - l + 1) * (d - u + 1) - 1;
}
}
return ret;
} else {
static int sum = -1;
static Vec<int> left, right, up, down;
if (sum == -1) {
left = right = up = down = Vec<int>(H * W);
sum = 0;
for (int i = 0; i < H * W; ++i) {
left[i] = right[i] = C[i];
up[i] = down[i] = R[i];
if (i > 0) {
left[i] = std::min(left[i], left[i - 1]);
right[i] = std::max(right[i], right[i - 1]);
up[i] = std::min(up[i], up[i - 1]);
down[i] = std::max(down[i], down[i - 1]);
}
sum += ((right[i] - left[i] + 1) * (down[i] - up[i] + 1) == i + 1);
}
}
if (a > b) {
std::swap(a, b);
}
for (int i = a; i <= b; ++i) {
sum -= ((right[i] - left[i] + 1) * (down[i] - up[i] + 1) == i + 1);
}
std::swap(C[a], C[b]);
std::swap(R[a], R[b]);
for (int i = a; i <= b; ++i) {
left[i] = right[i] = C[i];
up[i] = down[i] = R[i];
if (i > 0) {
left[i] = std::min(left[i], left[i - 1]);
right[i] = std::max(right[i], right[i - 1]);
up[i] = std::min(up[i], up[i - 1]);
down[i] = std::max(down[i], down[i - 1]);
}
sum += ((right[i] - left[i] + 1) * (down[i] - up[i] + 1) == i + 1);
}
return sum;
}
}
