#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pll;
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 1e6 + 10;
int n, m, R[MAXN], C[MAXN], k;
namespace segment {
pll sg[MAXN << 2];
int lz[MAXN << 2];
inline pll merge(pll a, pll b) {
if (a.X == b.X) return {a.X, a.Y + b.Y};
return min(a, b);
}
void build(int l = 0, int r = k - 1, int v = 1) {
if (l == r) sg[v] = {0, 1};
else {
int mid = (l + r) >> 1;
build(l, mid, v << 1);
build(mid + 1, r, v << 1 | 1);
sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
}
}
inline void push(int v) {
sg[v].X += lz[v];
if ((v << 1 | 1) < (MAXN << 2)) {
lz[v << 1] += lz[v];
lz[v << 1 | 1] += lz[v];
}
lz[v] = 0;
}
void update(int ql, int qr, int val, int l, int r, int v) {
push(v);
if (ql > r || qr < l) return;
if (ql <= l && qr >= r) {
lz[v] += val;
push(v);
return;
}
int mid = (l + r) >> 1;
update(ql, qr, val, l, mid, v << 1);
update(ql, qr, val, mid + 1, r, v << 1 | 1);
sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
}
void update(int l, int r, int val) {
if (r < l) return;
r = min(r, k-1);
update(l, r, val, 0, k-1, 1);
// cerr << l << sep << r << endl;
}
}
vector<vector<int>> A;
inline void add(int i, int j, int z) {
vector<int> vec;
for (int a = 0; a < 2; a++)
for (int b = 0; b < 2; b++)
vec.push_back({A[i + a][j + b]});
sort(all(vec));
segment::update(vec[0], vec[1] - 1, z);
segment::update(vec[2], vec[3] - 1, z);
}
void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_) {
n = H_, m = W_;
k = n * m;
segment::build();
A.resize(n + 5);
for (int i = 0; i < n + 5; i++) {
A[i].resize(m + 5, MAXN);
}
for (int i = 0; i < k; i++) {
R[i] = R_[i] + 1;
C[i] = C_[i] + 1;
A[R[i]][C[i]] = i;
}
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
add(i, j, 1);
}
int swap_seats(int a, int b) {
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
add(R[a] - i, C[a] - j, -1);
A[R[a]][C[a]] = b;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
add(R[a] - i, C[a] - j, 1);
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
add(R[b] - i, C[b] - j, -1);
A[R[b]][C[b]] = a;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
add(R[b] - i, C[b] - j, 1);
swap(R[a], R[b]);
swap(C[a], C[b]);
auto [_, cnt] = segment::sg[1];
return cnt;
}
