#include "seats.h"
#include <bits/stdc++.h>
using std::array;
using std::pair;
using std::vector;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
constexpr int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
class range_min {
int logn, size;
vector<int> data;
public:
range_min() = default;
explicit range_min(const int n) {
logn = 0;
while ((1 << logn) < n)
logn += 1;
size = 1 << logn;
data.resize(2 * size, inf);
}
void set(int i, const int x) {
i += size;
data[i] = x;
while (i > 1) {
i >>= 1;
data[i] = std::min(data[2 * i], data[2 * i + 1]);
}
}
int min() const { return data[1]; }
};
class lazy_segtree {
static constexpr pair<int, int> unit = {inf, 0};
int size, logn;
vector<pair<int, int>> data;
vector<int> lazy;
void apply(const int k, const int e) {
data[k].first += e;
if (k < size)
lazy[k] += e;
}
void flush(const int k) {
if (lazy[k] != 0) {
apply(2 * k, lazy[k]);
apply(2 * k + 1, lazy[k]);
lazy[k] = 0;
}
}
void push(const int k) {
const int lsb = __builtin_ctz(k);
for (int d = logn; d > lsb; --d)
flush(k >> d);
}
void fetch(const int k) {
const auto& [ml, cl] = data[2 * k];
const auto& [mr, cr] = data[2 * k + 1];
const int m = std::min(ml, mr);
data[k] = {m, (m == ml ? cl : 0) + (m == mr ? cr : 0)};
}
void pull(int k) {
k >>= __builtin_ctz(k);
while (k > 1)
fetch(k >>= 1);
}
public:
lazy_segtree() = default;
explicit lazy_segtree(const int n) {
logn = 0;
while ((1 << logn) < n)
logn += 1;
size = 1 << logn;
data.resize(2 * size, unit);
lazy.resize(size, 0);
for (int i = 0; i < n; ++i)
data[size + i] = {0, 1};
for (int i = size - 1; i > 0; --i)
fetch(i);
}
void add(int l, int r, const int x) {
l += size, r += size;
push(l), push(r);
const int lc = l, rc = r;
while (l < r) {
if (l & 1)
apply(l++, x);
if (r & 1)
apply(--r, x);
l >>= 1, r >>= 1;
}
pull(lc), pull(rc);
}
int get() const { return data[1].second; }
};
int H, W, N;
vector<int> R, C;
vector<vector<int>> grid;
vector<range_min> row, col;
lazy_segtree seg;
bool inside(const int i, const int j) {
return 0 <= i and i < H and 0 <= j and j < W;
}
int get(const int i, const int j) {
return inside(i, j) ? grid[i][j] : N;
}
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;
grid = vector(H, vector<int>(W));
row = vector(H, range_min(W));
col = vector(W, range_min(H));
seg = lazy_segtree(N);
for (int i = 0; i < N; ++i) {
grid[R[i]][C[i]] = i;
row[R[i]].set(C[i], i);
col[C[i]].set(R[i], i);
}
for (int i = 0; i < H; ++i)
seg.add(row[i].min(), N, -2);
for (int j = 0; j < W; ++j)
seg.add(col[j].min(), N, -2);
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
const int x = get(i, j);
for (int k = 0; k < 8; ++k) {
const int y = get(i + dx[k], j + dy[k]);
if (x < y)
seg.add(x, y, 1);
}
}
}
}
void update(const int i, const int j, const int c) {
const int x = get(i, j);
for (int k = 0; k < 8; ++k) {
const int y = get(i + dx[k], j + dy[k]);
seg.add(std::min(x, y), std::max(x, y), c);
}
}
void assign(const int i, const int j, const int x) {
seg.add(row[i].min(), N, 2);
seg.add(col[j].min(), N, 2);
update(i, j, -1);
grid[i][j] = x;
row[i].set(j, x);
col[j].set(i, x);
seg.add(row[i].min(), N, -2);
seg.add(col[j].min(), N, -2);
update(i, j, 1);
}
int swap_seats(int a, int b) {
assign(R[a], C[a], b);
assign(R[b], C[b], a);
std::swap(R[a], R[b]);
std::swap(C[a], C[b]);
return seg.get();
}
