#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
int h, w;
vector<int> r, c;
vector<vector<int>> g;
vector<pair<int,int>> st;
vector<int> lazy;
void pushdown(int node, int tl, int tr){
if (lazy[node] == 0) return;
if (tl != tr){
st[node*2].first += lazy[node];
lazy[node*2] += lazy[node];
st[node*2+1].first += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
void update(int l, int r, int v, int node=1, int tl=0, int tr=h*w-1){
pushdown(node, tl, tr);
if (l > r) return;
if (l <= tl && tr <= r){
st[node].first += v;
lazy[node] = v;
return;
}
int tm = (tl+tr)/2;
if (l <= tm) update(l, r, v, node*2, tl, tm);
if (tm+1 <= r) update(l, r, v, node*2+1, tm+1, tr);
if (st[node*2].first == st[node*2+1].first) st[node] = {st[node*2].first, st[node*2].second+st[node*2+1].second};
else st[node] = min(st[node*2], st[node*2+1]);
}
vector<int> fb(int t, int l){
vector<int> v = {g[t][l], g[t][l+1], g[t+1][l], g[t+1][l+1]};
sort(v.begin(), v.end());
return v;
}
void build(int node=1, int tl=0, int tr=h*w-1){
st[node].second = (tr-tl)+1;
if (tl == tr) return;
int tm = (tl+tr)/2;
build(node*2, tl, tm);
build(node*2+1, tm+1, tr);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H;
w = W;
r = R;
c = C;
g.resize(h+2, vector<int>(w+2, h*w));
for (int i=0; i<h*w; i++) g[r[i]+1][c[i]+1] = i;
st.resize(4*h*w, {0, 1});
build();
lazy.resize(4*h*w, 0);
for (int i=0; i<=h; i++){
for (int j=0; j<=w; j++){
vector<int> k = fb(i, j);
update(k[0], h*w-1, 1);
update(k[1], h*w-1, -1);
update(k[2], h*w-1, 1);
update(k[3], h*w-1, -1);
}
}
}
void cook(int a, int v){
for (int t = r[a]; t <= r[a]+1; t++){
for (int l = c[a]; l <= c[a]+1; l++){
vector<int> k = fb(t, l);
update(k[0], h*w-1, 1*v);
update(k[1], h*w-1, -1*v);
update(k[2], h*w-1, 1*v);
update(k[3], h*w-1, -1*v);
}
}
}
int swap_seats(int a, int b){
cook(a, -1);
cook(b, -1);
swap(g[r[a]+1][c[a]+1], g[r[b]+1][c[b]+1]);
swap(r[a], r[b]);
swap(c[a], c[b]);
cook(a, 1);
cook(b, 1);
return st[1].second;
}
