#include <bits/stdc++.h>
#include "seats.h"
#define ll long long
// #define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector<bool>
#define vvb vector<vb>;
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 1000000
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
vp t(4*MAXN+1);
int lazy[4*MAXN+1];
pii merge(pii a,pii b) {
if (a.F>b.F)return b;
if (a.F<b.F)return a;
return {a.F,a.S+b.S};
}
void build(int v,int tl,int tr) {
if (tl==tr)t[v]={0,1};else {
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v]=merge(t[v*2],t[v*2+1]);
}
}
void push(int v) {
t[2*v].F+=lazy[v];
t[2*v+1].F+=lazy[v];
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v]=0;
}
void up(int v,int tl,int tr,int l,int r,int delta) {
if (l>r)return;
if (tl==l && tr==r) {
t[v].F+=delta;
lazy[v]+=delta;
}else {
push(v);
int tm=(tl+tr)/2;
up(v*2,tl,tm,l,min(r,tm),delta);
up(v*2+1,tm+1,tr,max(l,tm+1),r,delta);
t[v]=merge(t[v*2],t[v*2+1]);
}
}
vvi arr;
vector <vector <bool>> seen;
int n,H,W;
void add(int x,int y,int t) {
vi v;
v.pb(arr[x][y]);
v.pb(arr[x+1][y]);
v.pb(arr[x][y+1]);
v.pb(arr[x+1][y+1]);
sort(v.begin(),v.end());
up(1,1,n,v[0],min(n,v[1]-1),t);
up(1,1,n,v[2],min(n,v[3]-1),t);
}
vi R,C;
void give_initial_chart(int h, int w, vi r, vi c) {
R=r;
C=c;
H=h;
W=w;
n=H*W;
build(1,1,n);
for (int i=0;i<=H+1;i++) {
vi cur;
vb CUR;
for (int j=0;j<=W+1;j++) {
cur.pb(0);
CUR.pb(false);
}
seen.pb(CUR);
arr.pb(cur);
}
for (int i=0;i<n;i++)arr[R[i]+1][C[i]+1]=i+1;
for (int i=0;i<=W+1;i++)arr[0][i]=INF,arr[H+1][i]=INF;
for (int i=0;i<=H+1;i++)arr[i][0]=INF,arr[i][W+1]=INF;
for (int i=0;i<=H;i++) {
for (int j=0;j<=W;j++) {
add(i,j,1);
}
}
// cout<<t[1].S;
}
int swap_seats(int a,int b) {
vp cur;
cur.pb({R[a]+1,C[a]+1});
cur.pb({R[a],C[a]+1});
cur.pb({R[a]+1,C[a]});
cur.pb({R[a],C[a]});
cur.pb({R[b]+1,C[b]+1});
cur.pb({R[b]+1,C[b]});
cur.pb({R[b],C[b]+1});
cur.pb({R[b],C[b]});
for (auto &[x,y]:cur){
if (!seen[x][y])add(x,y,-1);
seen[x][y]=true;
}
for (auto &[x,y]:cur)seen[x][y]=false;
swap(arr[R[a]+1][C[a]+1],arr[R[b]+1][C[b]+1]);
swap(R[a],R[b]);
swap(C[a],C[b]);
for (auto &[x,y]:cur){
if (!seen[x][y])add(x,y,1);
seen[x][y]=true;
}
for (auto &[x,y]:cur)seen[x][y]=false;
return t[1].S;
}
/*signed main(){
give_initial_chart(1,5,{0, 0, 0, 0, 0},{0, 1, 2, 3, 4});
cout<<swap_seats(0,1)<<'\n';
cout<<swap_seats(0,3)<<'\n';
cout<<swap_seats(4,0)<<'\n';
}*/
