#include <bits/stdc++.h>
#include "seats.h"
template <class T> using Vec = std::vector<T>;
constexpr int INF = std::numeric_limits<int>::max() / 2;
struct RMQ {
int size;
Vec<int> min, max;
RMQ() = default;
RMQ(const Vec<int>& vec): size(vec.size()), min(2 * vec.size(), INF), max(2 * vec.size(), INF) {
for (int i = 0; i < size; ++i) {
assign(i, vec[i]);
}
}
void assign(int i, const int x) {
i += size;
min[i] = max[i] = x;
while (i > 1) {
i >>= 1;
min[i] = std::min(min[2 * i], min[2 * i + 1]);
max[i] = std::max(max[2 * i], max[2 * i + 1]);
}
}
int diff(int l, int r) const {
l += size;
r += size;
int x = INF, y = -INF;
while (l < r) {
if (l & 1) {
x = std::min(x, min[l]);
y = std::max(y, max[l]);
l += 1;
}
if (r & 1) {
r -= 1;
x = std::min(x, min[r]);
y = std::max(y, max[r]);
}
l >>= 1;
r >>= 1;
}
return y - x + 1;
}
};
namespace {
int H, W;
Vec<int> R, C;
RMQ row, col;
};
void give_initial_chart(int h, int w, Vec<int> r, Vec<int> c) {
H = h, W = w;
R = r, C = c;
row = RMQ(R), col = RMQ(C);
}
int swap_seats(int a, int b) {
if (H + W <= 500) {
std::swap(R[a], R[b]);
std::swap(C[a], C[b]);
row.assign(a, R[a]);
col.assign(a, C[a]);
row.assign(b, R[b]);
col.assign(b, C[b]);
int ret = 0, cur = 0;
while (cur < H * W) {
const int area = row.diff(0, cur + 1) * col.diff(0, cur + 1);
if (area == cur + 1) {
ret += 1;
cur += 1;
} else {
cur = area - 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(R[a], R[b]);
std::swap(C[a], C[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;
}
}
