#include<iostream>
#include<algorithm>
#include<vector>
#include "seats.h"
using namespace std;
const int MAX_N=1e6+6;
int h,w;
struct V
{
pair<int,int>mi;
int cntmi,lazy1,lazy3;
};
V tree[4*MAX_N];
int r[MAX_N];
int c[MAX_N];
vector<vector<int>>id;
void push_lazy(int node,int l,int r)
{
tree[node].mi.first+=tree[node].lazy1;
tree[node].mi.second+=tree[node].lazy3;
if(l!=r)
{
tree[2*node].lazy1+=tree[node].lazy1;
tree[2*node].lazy3+=tree[node].lazy3;
tree[2*node+1].lazy1+=tree[node].lazy1;
tree[2*node+1].lazy3+=tree[node].lazy3;
}
tree[node].lazy1=0;
tree[node].lazy3=0;
}
void Update(int node,int l,int r,int ql,int qr,int l1,int l3)
{
push_lazy(node,l,r);
if(l>qr or r<ql)return;
if(ql<=l && r<=qr)
{
tree[node].lazy1+=l1;
tree[node].lazy3+=l3;
push_lazy(node,l,r);
return;
}
int mid=(l+r)/2;
Update(2*node,l,mid,ql,qr,l1,l3);
Update(2*node+1,mid+1,r,ql,qr,l1,l3);
tree[node].mi=min(tree[2*node].mi,tree[2*node+1].mi);
tree[node].cntmi=(tree[2*node].mi==tree[node].mi ? tree[2*node].cntmi : 0)+
(tree[2*node+1].mi==tree[node].mi ? tree[2*node+1].cntmi : 0);
}
vector<int>tmp;
void rem22(int row,int col)
{
tmp.clear();
tmp.push_back(id[row][col]);
tmp.push_back(id[row+1][col]);
tmp.push_back(id[row][col+1]);
tmp.push_back(id[row+1][col+1]);
sort(tmp.begin(),tmp.end());
if(tmp[0]<=tmp[1]-1)Update(1,0,h*w-1,tmp[0],tmp[1]-1,-1,0);
if(tmp[2]<=tmp[3]-1)Update(1,0,h*w-1,tmp[2],tmp[3]-1,0,-1);
}
void add22(int row,int col)
{
tmp.clear();
tmp.push_back(id[row][col]);
tmp.push_back(id[row+1][col]);
tmp.push_back(id[row][col+1]);
tmp.push_back(id[row+1][col+1]);
sort(tmp.begin(),tmp.end());
if(tmp[0]<=tmp[1]-1)Update(1,0,h*w-1,tmp[0],tmp[1]-1,+1,0);
if(tmp[2]<=tmp[3]-1)Update(1,0,h*w-1,tmp[2],tmp[3]-1,0,+1);
}
void rem(int row,int col)
{
rem22(row-1,col-1);
rem22(row-1,col);
rem22(row,col-1);
rem22(row,col);
}
void add(int row,int col)
{
add22(row-1,col-1);
add22(row-1,col);
add22(row,col-1);
add22(row,col);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
h=H;
w=W;
id.resize(h+5);
for(int i=0;i<h+5;i++)id[i].resize(w+5);
for(int i=0;i<h*w;i++)
{
r[i]=R[i]+1;
c[i]=C[i]+1;
id[r[i]][c[i]]=i;
}
for(int i=0;i<h+2;i++)
{
for(int j=0;j<w+2;j++)
{
if(i==0 or j==0 or i==h+1 or j==w+1)
{
id[i][j]=h*w;
}
}
}
for(int i=0;i<h*w;i++)
{
add(r[i],c[i]);
}
}
int swap_seats(int a, int b)
{
rem(r[a],c[a]);
rem(r[b],c[b]);
swap(id[r[a]][c[a]],id[r[b]][c[b]]);
swap(r[a],r[b]);
swap(c[a],c[b]);
add(r[a],c[a]);
add(r[b],c[b]);
return tree[1].cntmi;
}
