#include "seats.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
const int N=1e6+5;
int h,w,r[N],c[N],D[N];
vector<vector<int>> a;
int S[2*N];
pii pos[N],T[2*N];
pii mrg(pii A,pii B,int d){
A.fi+=d; B.fi+=d;
if(A.fi<B.fi) return A;
if(A.fi>B.fi) return B;
return pii(A.fi,A.se+B.se);
}
void init(int nd,int l,int r){
S[nd]=0;
if(l==r){
T[nd]=pii(D[l],1);
return;
}
int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
init(ln,l,m); init(rn,m+1,r);
T[nd]=mrg(T[ln],T[rn],0);
}
void add(int nd,int l,int r,int s,int e,int v){
if(r<s||e<l) return;
if(s<=l&&r<=e){
S[nd]+=v;
T[nd].fi+=v;
return;
}
int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
add(ln,l,m,s,e,v); add(rn,m+1,r,s,e,v);
T[nd]=mrg(T[ln],T[rn],S[nd]);
}
// (r, c) 오른쪽 아래의 꼭짓점.
void Do(int r,int c,int v=0){
// a[r][c] a[r][c+1]
// a[r+1][c] a[r+1][c+1]
vector<int> X;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) X.emplace_back(a[r+i][c+j]);
sort(X.begin(),X.end());
if(X[0]<h*w+1){
if(v) add(1,1,h*w,X[0],X[1]-1,v);
else{
D[X[0]]++;
D[X[1]]--;
}
}
if(X[2]<h*w+1){
if(v) add(1,1,h*w,X[2],X[3]-1,v);
else{
D[X[2]]++;
D[X[3]]--;
}
}
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
h=H;
w=W;
a.resize(h+2);
for(int i=0;i<=h+1;i++) a[i].resize(w+2);
for(int i=0;i<=h+1;i++) for(int j=0;j<=w+1;j++) a[i][j]=h*w+1;
for(int i=0;i<h*w;i++){
a[R[i]+1][C[i]+1]=i+1;
r[i+1]=R[i]+1;
c[i+1]=C[i]+1;
}
for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) Do(i,j);
for(int i=1;i<=h*w;i++) D[i]+=D[i-1];
init(1,1,h*w);
}
int swap_seats(int x,int y){
x++; y++;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[x]-i,c[x]-j,-1);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[y]-i,c[y]-j,-1);
swap(a[r[x]][c[x]],a[r[y]][c[y]]);
swap(r[x],r[y]);
swap(c[x],c[y]);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[x]-i,c[x]-j,1);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[y]-i,c[y]-j,1);
return T[1].se;
}
