#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e6 + 5;
int t[4 * mxN][2], lazy[4 * mxN];
void push(int x, int lx, int rx) {
if (lx == rx) return;
t[x << 1][0] += lazy[x];
t[x << 1 | 1][0] += lazy[x];
lazy[x << 1] += lazy[x];
lazy[x << 1 | 1] += lazy[x];
lazy[x] = 0;
}
void build(int x, int lx, int rx) {
if (lx == rx) {
t[x][1] = 1;
return;
}
int mx = (lx + rx) >> 1;
build(x << 1, lx, mx);
build(x << 1 | 1, mx + 1, rx);
t[x][1] = t[x << 1][1] + t[x << 1 | 1][1];
}
void update(int x, int lx, int rx, int l, int r, int del) {
if (lazy[x]) push(x, lx, rx);
if (l > rx || lx > r) return;
if (l <= lx && r >= rx) {
t[x][0] += del;
lazy[x] += del;
return;
}
int mx = (lx + rx) >> 1;
update(x << 1, lx, mx, l, r, del);
update(x << 1 | 1, mx + 1, rx, l, r, del);
t[x][0] = min(t[x << 1][0], t[x << 1 | 1][0]);
t[x][1] = 0;
if (t[x][0] == t[x << 1][0]) t[x][1] += t[x << 1][1];
if (t[x][0] == t[x << 1 | 1][0]) t[x][1] += t[x << 1 | 1][1];
}
vector<vector<int>> mat;
vector<int> r, c;
vector<vector<array<int, 2>>> all = {
{{-1, 0}, {-1, 1}, {0, 1}},
{{0, 1}, {1, 1}, {1, 0}},
{{1, 0}, {1, -1}, {0, -1}},
{{0, -1}, {-1, -1}, {-1, 0}}
};
int H, W;
void add(int x, int y, int del) {
if (!x || !y || x == H + 1 || y == W + 1) return;
for (int i = 0; i < 4; i++) {
int mx = H * W + 1;
for (auto a : all[i]) {
mx = min(mx, mat[x + a[0]][y + a[1]]);
}
if (mx > mat[x][y]) update(1, 1, H * W, mat[x][y] + 1, mx, del);
}
}
void give_initial_chart(int _H, int _W, std::vector<int> R, std::vector<int> C) {
H = _H, W = _W;
mat.assign(H + 2, vector<int> (W + 2, H * W));
for (int i = 0; i < H * W; i++) {
R[i]++, C[i]++;
mat[R[i]][C[i]] = i;
}
build(1, 1, H * W);
r = R, c = C;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
add(i, j, 1);
}
}
}
int swap_seats(int a, int b) {
vector<pair<int, int>> cells = {{r[a], c[a]}, {r[b], c[b]}};
for (int i = 0; i < 2; i++) {
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
int x = cells[i].first + dx, y = cells[i].second + dy;
cells.push_back({x, y});
}
}
}
sort(cells.begin(), cells.end());
cells.erase(unique(cells.begin(), cells.end()), cells.end());
for (auto [x, y] : cells) add(x, y, -1);
swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
for (auto [x, y] : cells) add(x, y, 1);
return t[1][1];
}
