#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN = 1e6+2;
int h, w;
vector<int> R, C;
vector<vector<int>> A;
pair<pii, int> seg[MXN<<2];
pii lz[MXN<<2];
inline pair<pii, int> merge(pair<pii, int> x, pair<pii, int> y) {
return x.X == y.X ? make_pair(x.X, x.Y+y.Y) : min(x, y);
}
void build(int l=0, int r=h*w, int id=1) {
lz[id] = {0, 0};
if(r-l == 1) {
seg[id] = {{0, 0}, 1};
return;
}
build(l, mid, lc);
build(mid, r, rc);
}
inline void apply(pii x, int id) {
seg[id].X.X += x.X; seg[id].X.Y += x.Y;
lz[id].X += x.X; lz[id].Y += x.Y;
}
inline void push(int id) {
if(lz[id].X || lz[id].Y) {
apply(lz[id], lc);
apply(lz[id], rc);
lz[id] = {0, 0};
}
}
void upd(int s, int e, pii x, int l=0, int r=h*w, int id=1) {
if(s>=r || l>=e) return;
if(s<=l && r<=e) {
apply(x, id);
return;
}
push(id);
upd(s, e, x, l, mid, lc);
upd(s, e, x, mid, r, rc);
seg[id] = merge(seg[lc], seg[rc]);
}
inline void add(int i, int j, int z) {
int mn1=h*w, mn2=h*w, mx1=0, mx2=0;
for(int k=max(0, i); k<=i+1 && k<h; k++)
for(int l=max(0, j), x; l<=j+1 && l<w; l++) {
x = 0<=k && k<h && 0<=l && l<w ? A[k][l] : h*w;
mn2 = min(mn2, x);
if(mn2<mn1) swap(mn1, mn2);
mx2 = max(mx2, x);
if(mx2>mx1) swap(mx1, mx2);
}
upd(mn1, mn2, {0, z});
if(0<=i && i+1<h && 0<=j && j+1<w) upd(mx2, mx1, {z, 0});
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
A = vector<vector<int>>(h=H, vector<int>(w=W));
::R = R;
::C = C;
for(int i=0; i<h*w; i++)
A[R[i]][C[i]] = i;
build();
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) {
add(R[a]-1, C[a]-1, -1);
add(R[a]-1, C[a], -1);
add(R[a], C[a]-1, -1);
add(R[a], C[a], -1);
add(R[b]-1, C[b]-1, -1);
add(R[b]-1, C[b], -1);
add(R[b], C[b]-1, -1);
add(R[b], C[b], -1);
swap(A[R[a]][C[a]], A[R[b]][C[b]]);
add(R[a]-1, C[a]-1, 1);
add(R[a]-1, C[a], 1);
add(R[a], C[a]-1, 1);
add(R[a], C[a], 1);
add(R[b]-1, C[b]-1, 1);
add(R[b]-1, C[b], 1);
add(R[b], C[b]-1, 1);
add(R[b], C[b], 1);
swap(R[a], R[b]);
swap(C[a], C[b]);
return seg[1].X == make_pair(0, 4) ? seg[1].Y : 0;
}
