#include "seats.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 1<<20;
namespace seg {
struct {
int mn, cnt, val;
} t[N*4];
int sz;
void merge(int i) {
t[i].mn = min(t[2*i+1].mn, t[2*i+2].mn);
t[i].cnt = (t[2*i+1].mn == t[i].mn? t[2*i+1].cnt: 0)
+ (t[2*i+2].mn == t[i].mn? t[2*i+2].cnt: 0);
t[i].mn += t[i].val;
}
void add(int l, int r, int x, int i, int b, int e) {
if (l <= b && e <= r) {
t[i].mn += x;
t[i].val += x;
return;
}
if (r <= b || e <= l)
return;
add(l, r, x, 2*i+1, b, (b+e)/2);
add(l, r, x, 2*i+2, (b+e)/2, e);
merge(i);
}
void add(int l, int r, int x) { if (l < r) add(l, r, x, 0, 0, sz); }
void init(int i, int b, int e) {
t[i].mn = t[i].val = 0;
t[i].cnt = e-b;
if (e-b > 1) {
init(2*i+1, b, (b+e)/2);
init(2*i+2, (b+e)/2, e);
}
}
void init(int n) { sz = n; init(0, 0, sz); }
}
vector<vector<int>> a;
pii pos[N];
int n, m;
bool in(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
void add_sq(int i, int j, int mul)
{
vector<int> vec;
Loop (x,i,i+2) Loop (y,j,j+2)
vec.push_back(in(x, y)? a[x][y]: n*m);
sort(vec.begin(), vec.end());
seg::add(vec[0], vec[1], mul);
seg::add(vec[2], vec[3], mul);
}
void add_adj(int i, int j, int mul)
{
Loop (x,i-1,i+1) Loop (y,j-1,j+1)
add_sq(x, y, mul);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H;
m = W;
a.assign(n, vector<int>(m));
Loop (i,0,n*m) {
pos[i] = {R[i], C[i]};
a[R[i]][C[i]] = i;
}
seg::init(n*m);
Loop (i,-1,n+1) Loop (j,-1,m+1)
add_sq(i, j, 1);
}
int swap_seats(int a, int b) {
auto [x1, y1] = pos[a];
auto [x2, y2] = pos[b];
add_adj(x1, y1, -1);
::a[x1][y1] = b;
add_adj(x1, y1, 1);
add_adj(x2, y2, -1);
::a[x2][y2] = a;
add_adj(x2, y2, 1);
swap(pos[a], pos[b]);
return seg::t[0].cnt;
}
