#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
struct nod{
int lo, am;
nod() {}
nod(int _lo, int _am) : lo(_lo), am(_am) {}
};
struct seg{
int n;
vector<nod> st;
vector<int> A, lazy;
seg(int sz) : n(sz), st(4*n), lazy(4*n) {}
seg(vector<int> ini) : seg((int)ini.size()) {
A = ini;
build(0,n-1,1);
}
nod mer(nod a, nod b){
nod c(min(a.lo,b.lo),0);
if(a.lo == c.lo)c.am+=a.am;
if(b.lo == c.lo)c.am+=b.am;
return c;
}
void build(int l, int r, int p){
if(l == r){
nod c(A[l],1);
st[p] = c;
return;
}
int m = (l+r)>>1;
build(l,m,p<<1);
build(m+1,r,(p<<1)+1);
st[p] = mer(st[p<<1],st[(p<<1)+1]);
}
void prop(int p){
if((p<<1)+1 < (int)lazy.size()){
lazy[p<<1]+=lazy[p];
lazy[(p<<1)+1]+=lazy[p];
}
lazy[p] = 0;
}
void update(int l, int r, int val, int lb, int rb, int p){
if(l > r)return;
st[p].lo+=lazy[p];
prop(p);
if(lb > r || rb < l)return;
if(lb >= l && rb <= r){
lazy[p] += val;
st[p].lo+=lazy[p];
prop(p);
return;
}
int m = (lb+rb)>>1;
update(l,r,val,lb,m,p<<1);
update(l,r,val,m+1,rb,(p<<1)+1);
st[p] = mer(st[p<<1],st[(p<<1)+1]);
}
void print(int l, int r, int p){
st[p].lo+=lazy[p];
prop(p);
if(l == r){
cout << st[p].lo << ' ';
return;
}
int m = (l+r)>>1;
print(l,m,p<<1);
print(m+1,r,(p<<1)+1);
}
};
seg ST(0);
vector<int> R, C;
map<pair<int,int>,int> M;
void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
R = r;
C = c;
vector<int> v(H*W);
int cu = -4;
set<pair<int,int>> S;
for(int i = 0; i < H*W; ++i){
S.insert({R[i],C[i]});
M[make_pair(R[i],C[i])] = i+1;
for(int x1 = -1; x1 <= 0; ++x1){
for(int y1 = -1; y1 <= 0; ++y1){
int cn = 0;
for(int x2 = 0; x2 < 2; ++x2){
for(int y2 = 0; y2 < 2; ++y2){
cn+=S.count({x1+x2+R[i],y1+y2+C[i]});
}
}
if(cn&1)cu++;
else cu--;
}
}
v[i] = cu;
}
ST = seg(v);
}
int swap_seats(int a, int b) {
int n = (int)R.size();
for(int x1 = -1; x1 <= 0; ++x1){
for(int y1 = -1; y1 <= 0; ++y1){
vector<int> z;
for(int x2 = 0; x2 < 2; ++x2){
for(int y2 = 0; y2 < 2; ++y2){
if(M[make_pair(x1+x2+R[a],y1+y2+C[a])])z.push_back(M[make_pair(x1+x2+R[a],y1+y2+C[a])]-1);
}
}
sort(z.begin(),z.end());
z.push_back(n);
for(int i = 0; i < (int)z.size()-1; i+=2){
ST.update(z[i],z[i+1]-1,(i&1 ? 1 : -1),0,n-1,1);
}
}
}
for(int x1 = -1; x1 <= 0; ++x1){
for(int y1 = -1; y1 <= 0; ++y1){
vector<int> z;
for(int x2 = 0; x2 < 2; ++x2){
for(int y2 = 0; y2 < 2; ++y2){
if(M[make_pair(x1+x2+R[b],y1+y2+C[b])])z.push_back(M[make_pair(x1+x2+R[b],y1+y2+C[b])]-1);
}
}
sort(z.begin(),z.end());
z.push_back(n);
for(int i = 0; i < (int)z.size()-1; i+=2){
ST.update(z[i],z[i+1]-1,(i&1 ? 1 : -1),0,n-1,1);
}
}
}
swap(M[{R[a],C[a]}],M[{R[b],C[b]}]);
swap(R[a],R[b]);
swap(C[a],C[b]);
for(int x1 = -1; x1 <= 0; ++x1){
for(int y1 = -1; y1 <= 0; ++y1){
vector<int> z;
for(int x2 = 0; x2 < 2; ++x2){
for(int y2 = 0; y2 < 2; ++y2){
if(M[make_pair(x1+x2+R[a],y1+y2+C[a])])z.push_back(M[make_pair(x1+x2+R[a],y1+y2+C[a])]-1);
}
}
sort(z.begin(),z.end());
z.push_back(n);
for(int i = 0; i < (int)z.size()-1; i+=2){
ST.update(z[i],z[i+1]-1,(i&1 ? -1 : 1),0,n-1,1);
}
}
}
for(int x1 = -1; x1 <= 0; ++x1){
for(int y1 = -1; y1 <= 0; ++y1){
vector<int> z;
for(int x2 = 0; x2 < 2; ++x2){
for(int y2 = 0; y2 < 2; ++y2){
if(M[make_pair(x1+x2+R[b],y1+y2+C[b])])z.push_back(M[make_pair(x1+x2+R[b],y1+y2+C[b])]-1);
}
}
sort(z.begin(),z.end());
z.push_back(n);
for(int i = 0; i < (int)z.size()-1; i+=2){
ST.update(z[i],z[i+1]-1,(i&1 ? -1 : 1),0,n-1,1);
}
}
}
return ST.st[1].am;
}
