#include "seats.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((ll)(bas+son)/2)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 1000000000000
#define N 1000005
#define MOD 998244353
using namespace std;
int h,w;
int ww[4][2]={1,1,-1,-1,-1,1,1,-1};
vector<vector<int>> a;
vector<int> r,c;
iii S[N*4];
ii lazy[N*4];
int eval() {
if(S[1].st.st==4 && S[1].st.nd==0) return S[1].nd;
return 0;
}
void shift(int node,ii lz) {
S[node].st.st+=lz.st;
S[node].st.nd+=lz.nd;
lazy[node].st+=lz.st;
lazy[node].nd+=lz.nd;
}
void push(int node) {
shift(node<<1,lazy[node]);
shift(node<<1|1,lazy[node]);
lazy[node]={0,0};
}
iii merge(iii a,iii b) {
if(a.st<b.st) return a;
if(b.st<a.st) return b;
return {a.st,a.nd+b.nd};
}
void up(int node,int bas,int son,int l,int r,ii lz) {
if(bas>r || son<l) return ;
if(bas>=l && son<=r) {
shift(node,lz);
return ;
}
push(node);
up(node<<1,bas,orta,l,r,lz);
up(node<<1|1,orta+1,son,l,r,lz);
S[node]=merge(S[node<<1],S[node<<1|1]);
}
void build(int node,int bas,int son) {
if(bas==son) {
S[node]={{0,0},1};
return ;
}
build(node<<1,bas,orta);
build(node<<1|1,orta+1,son);
S[node]=merge(S[node<<1],S[node<<1|1]);
}
int gtot(int xa,int ya,int xb,int yb) {
int tot=0;
if(xa>xb) swap(xa,xb);
if(ya>yb) swap(ya,yb);
for(int i=xa;i<=xb;i++) {
for(int j=ya;j<=yb;j++) {
tot+=(a[i][j]!=-1);
}
}
return tot;
}
void upd(int x,int y,int val,int sg) {
if(val==-1) return ;
int cnt[2][2]={0};
for(int i=0;i<4;i++) {
int tot=gtot(x+ww[i][0],y+ww[i][1],x,y);
if(tot==1) cnt[0][0]++;
if(tot==3) cnt[0][1]++;
}
a[x][y]=val;
for(int i=0;i<4;i++) {
int tot=gtot(x+ww[i][0],y+ww[i][1],x,y);
if(tot==1) cnt[1][0]++;
if(tot==3) cnt[1][1]++;
}
up(1,0,h*w-1,val,h*w-1,{sg*(cnt[1][0]-cnt[0][0]),sg*(cnt[1][1]-cnt[0][1])});
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H;
w=W;
a=vector<vector<int>>(h+5,vector<int>(w+5,-1));
r=c=vector<int>(h*w+5);
build(1,0,h*w-1);
for(int i=0;i<h*w;i++) {
r[i]=R[i]+1;
c[i]=C[i]+1;
upd(r[i],c[i],i,1);
}
}
void upcr(int x,vector<pair<int,ii>>&cr) {
for(int i=r[x]-1;i<=r[x]+1;i++) {
for(int j=c[x]-1;j<=c[x]+1;j++) {
cr.pb({a[i][j],{i,j}});
}
}
}
void make_minus(vector<pair<int,ii>>& cr) {
for(auto x:cr) a[x.nd.st][x.nd.nd]=-1;
}
int swap_seats(int x, int y) {
#define iii pair<int,ii>
vector<iii> cr;
upcr(x,cr);
upcr(y,cr);
sort(cr.begin(),cr.end());
cr.erase(unique(cr.begin(),cr.end()),cr.end());
make_minus(cr);
for(auto x:cr) {
upd(x.nd.st,x.nd.nd,x.st,-1);
}
swap(r[x],r[y]);
swap(c[x],c[y]);
for(auto& x:cr) {
tie(x.nd.st,x.nd.nd)={r[x.st],c[x.st]};
}
make_minus(cr);
for(auto x:cr) {
upd(x.nd.st,x.nd.nd,x.st,1);
}
return eval();
}
