#include "seats.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;
const int ruin = 10; ///anything >= 4
vector<vector<int> > arr;
ii pos[1000005];
int rows, cols;
int n;
inline ii merge(ii a, ii b){
if(a.first == b.first) return ii(a.first, a.second+b.second);
else return min(a, b);
}
struct node{
int s, e, m;
ii val; int lazy;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
val = ii(0,e-s+1), lazy = 0;
if(s != e) l = new node(s, m), r = new node(m+1, e);
}
void apply(int L){
lazy += L;
val.first += L;
}
void push(){
if(s != e && lazy != 0){
l->apply(lazy);
r->apply(lazy);
lazy = 0;
}
}
void update(int S, int E, int L){
if(S > E) return;
push();
if(S == s && e == E){
apply(L);
return;
}
if(E <= m) l->update(S, E, L);
else if(S >= m+1) r->update(S, E, L);
else{
l->update(S, m, L);
r->update(m+1, E, L);
}
val = merge(l->val, r->val);
}
int query(){
push();
return val.second;
}
} *root;
inline void update(int R, int C, bool undo){
vector<int> v = {arr[R][C], arr[R][C+1], arr[R+1][C], arr[R+1][C+1]};
sort(all(v));
int a = v[0], b = v[1], c = v[2], d = v[3];
//cout << a << " " << b << " " << c << " " << d << endl;
if(undo){
root->update(a, b-1, -1);
root->update(c, d-1, -ruin);
}
else{
root->update(a, b-1, 1);
root->update(c, d-1, ruin);
}
}
inline void square(ii x, bool undo){
int r = x.first, c = x.second;
update(r, c, undo);
update(r-1, c, undo);
update(r, c-1, undo);
update(r-1, c-1, undo);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
rows = H, cols = W, n = rows*cols;
arr.resize(rows+2);
for(int i = 0;i <= rows+1;i++){
arr[i].assign(cols+2, n);
}
for(int i = 0;i < n;i++){
int r = R[i]+1, c = C[i]+1;
arr[r][c] = i;
pos[i] = ii(r,c);
}
root = new node(0, n-1);
for(int r = 0;r <= rows;r++){
for(int c = 0;c <= cols;c++){
update(r, c, false);
}
}
//cout << root->query() << '\n';
}
int swap_seats(int a, int b){
ii A = pos[a], B = pos[b];
square(A, true); square(B, true);
swap(pos[a], pos[b]);
arr[A.first][A.second] = b;
arr[B.first][B.second] = a;
square(A, false); square(B, false);
return root->query();
}
