#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1e6+99,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,m,A[N],B[N],p[N],lz[N<<2];
pair<int,int> seg[N<<2];
pair<int,int> operator + (pair<int,int> a,pair<int,int> b){
if(a.F==b.F) return {a.F,b.S+a.S};
if(a<b) return a;
else return b;
}
void shift(int id){
seg[id<<1].F+=lz[id];
seg[id<<1|1].F+=lz[id];
lz[id<<1]+=lz[id];
lz[id<<1|1]+=lz[id];
lz[id]=0;
}
void build(int id=1,int l=0,int r=n*m){
seg[id]={0,r-l};
if(l+1==r) return ;
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid,r);
}
void add(int L,int R,int val,int id=1,int l=0,int r=n*m){
if(r<=L || R<=l) return ;
if(L<=l && r<=R){
lz[id]+=val;
seg[id].F+=val;
return ;
}
shift(id);
int mid=(l+r)>>1;
add(L,R,val,id<<1,l,mid);
add(L,R,val,id<<1|1,mid,r);
seg[id]=seg[id<<1]+seg[id<<1|1];
}
bool ini(int x,int y){
return 0<=x && x<n && 0<=y && y<m;
}
int dist(int x,int y){
return abs(x-A[0])+abs(y-B[0]);
}
void Add(int x,int y,int u,int v){
if(dist(x,y)>dist(u,v)) swap(x,u),swap(y,v);
if(p[v]<p[y]){
//cout<<p[u][v]<<" -> "<<p[x][y]<<'\n';
add(p[v],p[y],1);
}
}
void Del(int x,int y,int u,int v){
if(dist(x,y)>dist(u,v)) swap(x,u),swap(y,v);
if(p[v]<p[y]){
add(p[v],p[y],-1);
}
}
void pAdd(int a,int b){
f(i,0,4){
int x=A[a]+dx[i],y=B[a]+dy[i];
if(ini(x,y)==0 || p[y]==b) continue ;
Add(A[a],B[a],x,y);
}
}
void pDel(int a,int b){
f(i,0,4){
int x=A[a]+dx[i],y=B[a]+dy[i];
if(ini(x,y)==0 || p[y]==b) continue ;
Del(A[a],B[a],x,y);
}
}
void give_initial_chart(int _n,int _m,vector<int> _A,vector<int> _B) {
n=_n,m=_m;
f(i,0,n*m){
A[i]=_A[i],B[i]=_B[i];
p[B[i]]=i;
}
build();
f(i,0,m-1){
Add(0,i,0,i+1);
}
//erorp(seg[1]);
}
int swap_seats(int a, int b){
pDel(a,a);
pDel(b,a);
swap(p[B[a]],p[B[b]]);
swap(B[a],B[b]);
pAdd(a,a);
pAdd(b,a);
return seg[1].S*(seg[1].F==0);
}
/*
1 6 0
0 0
0 3
0 5
0 4
0 1
0 2
1 6 2
0 2
0 3
0 5
0 4
0 1
0 0
0 5
0 5
*/
