#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int h, w, n;
vector<pii> vect;
vector<vector<int> > graph;
struct node{
int s, e, m, lazy;
pii val;
node *l, *r;
void propagate(){
val.fi+=lazy;
if (s!=e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
node(int S, int E){
s = S, e = E, m = (s+e)/2;
val.fi=lazy=0;
val.se=e-s+1;
if (s!=e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void up(int left, int right, int v){
if (left>right)return;
propagate();
if (s==left && e==right)lazy+=v;
else{
if (right<=m)l->up(left, right, v);
else if (left>m)r->up(left, right, v);
else l->up(left, m, v), r->up(m+1, right, v);
r->propagate(), l->propagate();
if (l->val.fi==r->val.fi)val=mp(l->val.fi, l->val.se+r->val.se);
else val=min(l->val, r->val);
}
}
}*st;
void update(int x, int y, int v){
vector<int> temp;
temp.pb(graph[x][y]);
temp.pb(graph[x+1][y]);
temp.pb(graph[x][y+1]);
temp.pb(graph[x+1][y+1]);
sort(temp.begin(), temp.end());
st->up(temp[0], temp[1]-1, v);
st->up(temp[2], temp[3]-1, 5*v);
}
void add(int x, int y, int v){
update(x, y, v);
update(x-1, y, v);
update(x, y-1, v);
update(x-1, y-1, v);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h=H, w=W, n=h*w;
vect.resize(n);
graph.resize(h+2, vector<int>(w+2, h*w));
st = new node(0, n-1);
for (int i=0; i<n; ++i){
vect[i]=mp(R[i]+1, C[i]+1);
graph[R[i]+1][C[i]+1]=i;
}
for (int i=0; i<=h; ++i)for (int j=0; j<=W; ++j)update(i, j, 1);
}
int swap_seats(int a, int b){
add(vect[a].fi, vect[a].se, -1);
add(vect[b].fi, vect[b].se, -1);
swap(graph[vect[a].fi][vect[a].se], graph[vect[b].fi][vect[b].se]);
swap(vect[a], vect[b]);
add(vect[a].fi, vect[a].se, 1);
add(vect[b].fi, vect[b].se, 1);
st->propagate();
if (st->val.fi==4)return st->val.se;
return 0;
}
