#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define set(x,a,b,c,d) x[0]=a,x[1]=b,x[2]=c,x[3]=d;
const int inf = 1e9;
const int sz = 1<<20;
struct node {
int mn=inf, cnt=0;
node(int a, int b) {mn=a,cnt=b;}
node() {}
};
node t[2*sz];
int lazy[4*sz];
void build(int v, int l, int r) {
if (r-l==1) return;
int m=(l+r)>>1;
build(2*v+1,l,m);
build(2*v+2,m,r);
if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
else t[v]=t[2*v+2];
}
void init(int n, int m) {
forn(i,n*m) t[sz-1+i]={0,1};
build(0,0,sz);
}
void add(int v, int l, int r, int lx, int rx, int x) {
if (lazy[v]) {
t[v].mn+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[2*v+2]+=lazy[v];
lazy[v]=0;
}
if (rx<=l || r<=lx) return;
if (lx<=l && r<=rx) {
t[v].mn+=x;
lazy[2*v+1]+=x;
lazy[2*v+2]+=x;
return;
}
int m=(l+r)>>1;
add(2*v+1,l,m,lx,rx,x);
add(2*v+2,m,r,lx,rx,x);
if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
else t[v]=t[2*v+2];
}
void add(int l, int r, int x) {
if (l>=r) return;
add(0,0,sz,l,r,x);
}
int R[sz], C[sz];
int swapped=0;
int n,m;
vector<vector<int>> a;
int z[4];
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
n=_n, m=_m;
if (n==1 && m==1) return;
forn(i,n*m) R[i]=_r[i]+1, C[i]=_c[i]+1;
if (m==1) {
swap(n,m);
forn(i,n*m) swap(R[i],C[i]);
swapped=1;
}
init(n,m);
a.assign(n+2,vector<int>(m+2,n*m));
forn(i,n*m) a[R[i]][C[i]]=i;
for (int i=0; i<=n; ++i) {
for (int j=0; j<=m; ++j) {
set(z,a[i][j],a[i+1][j],a[i][j+1],a[i+1][j+1]);
sort(z,z+4);
add(z[0],z[1],1);
add(z[2],z[3],1);
}
}
}
int swap_seats(int x, int y) {
if (n==1 && m==1) return 1;
int p=R[x], q=C[x], u=R[y], v=C[y];
set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]);
sort(z,z+4);
add(z[0],z[1],-1);
add(z[2],z[3],-1);
set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]);
sort(z,z+4);
add(z[0],z[1],-1);
add(z[2],z[3],-1);
set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]);
sort(z,z+4);
add(z[0],z[1],-1);
add(z[2],z[3],-1);
set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]);
sort(z,z+4);
add(z[0],z[1],-1);
add(z[2],z[3],-1);
p=u, q=v;
set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]);
sort(z,z+4);
add(z[0],z[1],-1);
add(z[2],z[3],-1);
set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]);
sort(z,z+4);
add(z[0],z[1],-1);
add(z[2],z[3],-1);
set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]);
sort(z,z+4);
add(z[0],z[1],-1);
add(z[2],z[3],-1);
set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]);
sort(z,z+4);
add(z[0],z[1],-1);
add(z[2],z[3],-1);
swap(R[x],R[y]);
swap(C[x],C[y]);
a[R[x]][C[x]]=x;
a[R[y]][C[y]]=y;
p=R[x], q=C[x], u=R[y], v=C[y];
set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]);
sort(z,z+4);
add(z[0],z[1],1);
add(z[2],z[3],1);
set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]);
sort(z,z+4);
add(z[0],z[1],1);
add(z[2],z[3],1);
set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]);
sort(z,z+4);
add(z[0],z[1],1);
add(z[2],z[3],1);
set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]);
sort(z,z+4);
add(z[0],z[1],1);
add(z[2],z[3],1);
p=u, q=v;
set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]);
sort(z,z+4);
add(z[0],z[1],1);
add(z[2],z[3],1);
set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]);
sort(z,z+4);
add(z[0],z[1],1);
add(z[2],z[3],1);
set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]);
sort(z,z+4);
add(z[0],z[1],1);
add(z[2],z[3],1);
set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]);
sort(z,z+4);
add(z[0],z[1],1);
add(z[2],z[3],1);
return t[0].cnt;
}
