#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mid ((l+r) >> 1)
const int dx[4] = {0, 0, -1, -1}, dy[4] = {0, -1, 0, -1}, S[4] = {1, -1, 5, -5};
array<int, 2> t[4004004];
int lz[4004004];
int n, h, w, x[1001001], y[1001001], cb, cw;
vector<vector<int>> mp;
void lazy_update(int node, int l, int r) {
if(!lz[node]) return;
t[node][0] += lz[node];
if(l != r) lz[node*2] += lz[node], lz[node*2+1] += lz[node];
lz[node] = 0;
}
void update(int nl, int nr, int val, int node = 1, int l = 0, int r = n-1) {
lazy_update(node, l, r);
if(nr < l || r < nl) return;
if(nl <= l && r <= nr) {
lz[node] += val;
lazy_update(node, l, r);
return;
}
update(nl, nr, val, node*2, l, mid), update(nl, nr, val, node*2+1, mid+1, r);
if(t[node*2][0] == t[node*2+1][0]) t[node] = t[node*2], t[node][1] += t[node*2+1][1];
else t[node] = min(t[node*2], t[node*2+1]);
}
void build(int node = 1, int l = 0, int r = n-1) {
t[node][1] = r-l+1;
if(l == r) return;
build(node*2, l, mid), build(node*2+1, mid+1, r);
}
void query(int x, int y, int k) {
int p[4] = {mp[x][y], mp[x+1][y], mp[x][y+1], mp[x+1][y+1]};
for(int i=0;i<4;i++) for(int j=i+1;j<4;j++) if(p[i] > p[j]) swap(p[i], p[j]);
for(int i=0;i<4;i++) update(p[i], n-1, S[i]*k);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H*W, h = H, w = W;
for(int i=0;i<n;i++) x[i] = R[i]+1, y[i] = C[i]+1;
mp.resize(h+2, vector<int>(w+2, n));
build();
for(int i=0;i<n;i++) mp[x[i]][y[i]] = i;
for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) query(i, j, 1);
}
int swap_seats(int a, int b) {
for(int i=0;i<4;i++) query(x[a]+dx[i], y[a]+dy[i], -1);
for(int i=0;i<4;i++) query(x[b]+dx[i], y[b]+dy[i], -1);
swap(x[a], x[b]), swap(y[a], y[b]);
swap(mp[x[a]][y[a]], mp[x[b]][y[b]]);
for(int i=0;i<4;i++) query(x[a]+dx[i], y[a]+dy[i], 1);
for(int i=0;i<4;i++) query(x[b]+dx[i], y[b]+dy[i], 1);
return t[1][1];
}
