#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
int n,m;
vector <vector <int> > grid;
vector <vector <array <int,4> > > v;
vector <pair <int,int> > pos;
int mn[12000100],cntmn[12000100],laz[12000100];
void pushup(int id){
mn[id]=min(mn[2*id],mn[2*id+1]);
cntmn[id]=0;
if (mn[2*id]==mn[id]) cntmn[id]+=cntmn[2*id];
if (mn[2*id+1]==mn[id]) cntmn[id]+=cntmn[2*id+1];
}
void pushdown(int id){
mn[2*id]+=laz[id];
mn[2*id+1]+=laz[id];
laz[2*id]+=laz[id];
laz[2*id+1]+=laz[id];
laz[id]=0;
}
void build(int id,int tl,int tr){
if (tl==tr){
mn[id]=0; cntmn[id]=1; laz[id]=0;
return;
}
int tm=(tl+tr)/2;
build(2*id,tl,tm);
build(2*id+1,tm+1,tr);
pushup(id);
}
void update(int id,int tl,int tr,int l,int r,int val){
if (l>r) return;
if (l<=tl&&tr<=r){
mn[id]+=val; laz[id]+=val;
return;
}
pushdown(id);
int tm=(tl+tr)/2;
update(2*id,tl,tm,l,min(r,tm),val);
update(2*id+1,tm+1,tr,max(l,tm+1),r,val);
pushup(id);
}
void add(int l,int r,int val){
update(1,1,(n+1)*(m+1),l,r,val);
}
void give_initial_chart(int H,int W,vector <int> R,vector <int> C){
n=H; m=W; grid.clear(); v.clear();
vector <int> tp(m+2,inf);
for (int i=0; i<=n+1; i++) grid.push_back(tp);
pos.push_back({0,0});
for (int i=0; i<H*W; i++){
grid[R[i]+1][C[i]+1]=i+1;
pos.push_back({R[i]+1,C[i]+1});
}
vector <array <int,4> > tt(m+2,{inf,inf,inf,inf});
for (int i=0; i<=n+1; i++) v.push_back(tt);
for (int i=1; i<=n+1; i++){
for (int j=1; j<=m+1; j++){
int cnt=0;
for (int d=-1; d<=0; d++){
for (int e=-1; e<=0; e++){
v[i][j][cnt++]=grid[i+d][j+e];
}
}
sort(v[i][j].begin(),v[i][j].end());
}
}
build(1,1,(n+1)*(m+1));
for (int i=1; i<=n+1; i++){
for (int j=1; j<=m+1; j++){
if (v[i][j][0]<inf){
add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),1);
}
if (v[i][j][2]<inf){
add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),1);
}
}
}
}
int swap_seats(int a, int b){
a++; b++;
for (int i=pos[a].first; i<=pos[a].first+1; i++){
for (int j=pos[a].second; j<=pos[a].second+1; j++){
if (v[i][j][0]<inf){
add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),-1);
}
if (v[i][j][2]<inf){
add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),-1);
}
v[i][j]={inf,inf,inf,inf};
}
}
for (int i=pos[b].first; i<=pos[b].first+1; i++){
for (int j=pos[b].second; j<=pos[b].second+1; j++){
if (v[i][j][0]==inf) continue;
if (v[i][j][0]<inf){
add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),-1);
}
if (v[i][j][2]<inf){
add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),-1);
}
v[i][j]={inf,inf,inf,inf};
}
}
swap(grid[pos[a].first][pos[a].second],grid[pos[b].first][pos[b].second]);
swap(pos[a],pos[b]);
for (int i=pos[a].first; i<=pos[a].first+1; i++){
for (int j=pos[a].second; j<=pos[a].second+1; j++){
int cnt=0;
for (int d=-1; d<=0; d++){
for (int e=-1; e<=0; e++){
v[i][j][cnt++]=grid[i+d][j+e];
}
}
sort(v[i][j].begin(),v[i][j].end());
if (v[i][j][0]<inf){
add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),1);
}
if (v[i][j][2]<inf){
add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),1);
}
}
}
for (int i=pos[b].first; i<=pos[b].first+1; i++){
for (int j=pos[b].second; j<=pos[b].second+1; j++){
if (v[i][j][0]!=inf) continue;
int cnt=0;
for (int d=-1; d<=0; d++){
for (int e=-1; e<=0; e++){
v[i][j][cnt++]=grid[i+d][j+e];
}
}
sort(v[i][j].begin(),v[i][j].end());
if (v[i][j][0]<inf){
add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),1);
}
if (v[i][j][2]<inf){
add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),1);
}
}
}
return cntmn[1]-(n+1)*(m+1)+n*m;
}
