#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define pb push_back
#define F first
#define S second
#define lc v<<1
#define rc v<<1|1
const int N = 1e6 + 10, inf = 1.05e9;
int n,m,lz[N*4],dx[]={0,0,1,1},dy[]={0,1,1,0},s;
pii f[N*4];
vector<int> A[N],r,c;
void build(int v, int l, int r){
f[v].S=r-l;
if(r-l==1) return;
int m=(l+r)>>1;
build(lc,l,m);
build(rc,m,r);
}
void shift(int v, int l, int r){
f[v].F+=lz[v];
if(r-l>1){
lz[lc]+=lz[v];
lz[rc]+=lz[v];
}
lz[v]=0;
}
void upd(int v, int l, int r, int tl, int tr, int x){
shift(v,l,r);
if(l>=tr || tl>=r || tl>=tr) return;
if(l>=tl && r<=tr){
lz[v]=x;
return shift(v,l,r);
}
int m=(l+r)>>1;
upd(lc,l,m,tl,tr,x);
upd(rc,m,r,tl,tr,x);
f[v].F=min(f[lc].F,f[rc].F);
f[v].S=0;
if(f[v].F==f[lc].F) f[v].S+=f[lc].S;
if(f[v].F==f[rc].F) f[v].S+=f[rc].S;
}
void calc(int x, int y, int k){
vector<int> vec;
for(int i=0; i<4; i++){
vec.pb(A[x+dx[i]][y+dy[i]]);
}
sort(vec.begin(),vec.end());
upd(1,0,s,vec[0],vec[1],k);
upd(1,0,s,vec[2],vec[3],k);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n=H;
m=W;
r=R;
c=C;
s=n*m;
build(1,0,s);
for(int i=0; i<=n+1; i++) A[i].resize(m+2,inf);
for(int i=0; i<s; i++){
r[i]++;
c[i]++;
A[r[i]][c[i]]=i;
}
for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) calc(i,j,1);
}
int swap_seats(int a, int b) {
for(int i=0; i<4; i++){
calc(r[a]-dx[i],c[a]-dy[i],-1);
calc(r[b]-dx[i],c[b]-dy[i],-1);
}
swap(A[r[a]][c[a]],A[r[b]][c[b]]);
swap(r[a],r[b]);
swap(c[a],c[b]);
for(int i=0; i<4; i++){
calc(r[a]-dx[i],c[a]-dy[i],1);
calc(r[b]-dx[i],c[b]-dy[i],1);
}
return f[1].S;
}
