#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int h, w, n;
vi r, c;
vector<vi> A;
int dx[]={-1, 0, 1, 0};
int dy[]={ 0,-1, 0, 1};
vi SEG, SEGMIN, SEGCNT;
void updateNode(int p) {
SEG [p] = 0;
SEGMIN[p] = min(SEGMIN[p*2+1], SEGMIN[p*2+2]);
SEGCNT[p] = 0;
if(SEGMIN[p*2+1] == SEGMIN[p]) SEGCNT[p] += SEGCNT[p*2+1];
if(SEGMIN[p*2+2] == SEGMIN[p]) SEGCNT[p] += SEGCNT[p*2+2];
}
void buildSeg(int p=0, int L=0, int R=n-1) {
if(L == R) {
SEG[p] = 0;
SEGMIN[p] = 0;
SEGCNT[p] = 1;
return;
}
int m=(L+R)/2;
buildSeg(p*2+1,L,m);
buildSeg(p*2+2,m+1,R);
updateNode(p);
}
void addSeg(int i, int j, int x, int lazy=0, int p=0, int L=0, int R=n-1) {
SEG [p] += lazy;
SEGMIN[p] += lazy;
if(j < L || i > R) return;
if(i <= L && j >= R) {
SEG [p] += x;
SEGMIN[p] += x;
return;
}
int m=(L+R)/2;
addSeg(i,j,x,SEG[p],p*2+1,L,m);
addSeg(i,j,x,SEG[p],p*2+2,m+1,R);
updateNode(p);
}
int getEnd(ii pos) {
if(pos.fi < 0 || pos.fi >= h) return n-1;
if(pos.se < 0 || pos.se >= w) return n-1;
return A[pos.fi][pos.se]-1;
}
void updateNeigbours(ii cent, ii pos1, ii pos2, int x=1) {
if(getEnd(cent) == n-1) return;
int bg = A[cent.fi][cent.se];
int ed = min(getEnd(pos1), getEnd(pos2));
if(ed >= bg) addSeg(bg, ed, x);
bg = max(getEnd(pos1), getEnd(pos2))+1;
ed = A[cent.fi][cent.se]-1;
if(ed >= bg) addSeg(bg, ed, x);
}
void updateNeigbours(ii cent, int d, int x=1) {
int d1 = d;
int d2 = (d+1)%4;
ii pos1 = {cent.fi+dx[d1], cent.se+dy[d1]};
ii pos2 = {cent.fi+dx[d2], cent.se+dy[d2]};
updateNeigbours(cent, pos1, pos2, x);
}
void give_initial_chart(int H, int W, vi R, vi C) {
h=H, w=W, r=R, c=C;
n = h*w;
A.resize(h);
RE(i,h) A[i].resize(w);
RE(i,n) A[r[i]][c[i]] = i;
SEG .resize(n*4);
SEGMIN.resize(n*4);
SEGCNT.resize(n*4);
buildSeg();
RE(i,h) RE(j,w) RE(k,4) updateNeigbours({i,j}, k);
}
int swap_seats(int a, int b) {
set<pair<ii, int>> updated;
// a's neighbours
RE(i,4) updated.insert({{r[a],c[a]}, i});
RE(i,4) {
ii cent = {r[a]+dx[i],c[a]+dy[i]};
RE(j,4) updated.insert({cent, j});
}
// b's neighbours
RE(i,4) updated.insert({{r[b],c[b]}, i});
RE(i,4) {
ii cent = {r[b]+dx[i],c[b]+dy[i]};
RE(j,4) updated.insert({cent, j});
}
for(auto p : updated) updateNeigbours(p.fi, p.se, -1);
swap(r[a], r[b]);
swap(c[a], c[b]);
A[r[a]][c[a]] = a;
A[r[b]][c[b]] = b;
for(auto p : updated) updateNeigbours(p.fi, p.se, 1);
if(SEGMIN[0] != 4) return 0;
else return SEGCNT[0];
}
