#include "seats.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
struct SEGMENT_TREE{
struct NODE{
int st, fin, minnum;
pii minn, lazy;
}tree[4000010];
int x;
void maketree(int point, int num) {
if(num==1){
tree[point].st=tree[point].fin=++x;
tree[point].minnum=1;
}
if(num<=1)return;
maketree(point*2, num-num/2);
maketree(point*2+1, num/2);
tree[point].st=tree[point*2].st;
tree[point].fin=tree[point*2+1].fin;
}
pii ADD(pii &a, pii b){
a.F+=b.F;
a.S+=b.S;
}
void propogate(int point){
ADD(tree[2*point].minn, tree[point].lazy);
ADD(tree[2*point+1].minn, tree[point].lazy);
ADD(tree[2*point].lazy, tree[point].lazy);
ADD(tree[2*point+1].lazy, tree[point].lazy);
tree[point].lazy=pii(0, 0);
}
void relaxnode(int point){
tree[point].minn=min(tree[point*2].minn, tree[point*2+1].minn);
tree[point].minnum=0;
if(tree[point].minn==tree[point*2].minn)tree[point].minnum+=tree[point*2].minnum;
if(tree[point].minn==tree[point*2+1].minn)tree[point].minnum+=tree[point*2+1].minnum;
}
void alterrange(int point, int a, int b, pii p) {
if(tree[point].fin<a||tree[point].st>b)return;
if(tree[point].st>=a&&tree[point].fin<=b) {
ADD(tree[point].minn, p);
ADD(tree[point].lazy, p);
return;
}
propogate(point);
alterrange(point*2, a, b, p);
alterrange(point*2+1, a, b, p);
relaxnode(point);
}
int query(){
return tree[1].minn==pii(4, 0)?tree[1].minnum:0;
}
}seg;
vector<vector<int> > grid;
vector<int> r, c;
int n, m;
void updatepoint(int x, int y, int p)
{
vector<int> temp;
for(int i=-1; i<=0; i++)
for(int j=-1; j<=0; j++)
temp.pb(grid[x+i][y+j]);
sort(all(temp));
seg.alterrange(1, temp[0], temp[1], pii(p, 0));
seg.alterrange(1, temp[2], temp[3], pii(0, p));
}
void update(int x, int y, int p)
{
for(int i=0; i<=1; i++)
for(int j=0; j<=1; j++)
updatepoint(x+i, y+j, p);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n=H;
m=W;
r=R;
c=C;
grid.resize(n+2);
for(int i=0; i<grid.size(); i++)grid[i].resize(m+2);
for(int i=0; i<grid.size(); i++)
for(int j=0; j<grid[i].size(); j++)
grid[i][j]=n*m;
for(int i=0; i<n*m; i++){
grid[r[i]+1][c[i]+1]=i;
}
seg.maketree(1, n*m);
for(int i=0; i<=n; i++){
for(int j=0; j<=m; j++){
update(i, j, 1);
}
}
}
int swap_seats(int a, int b){
for(int i=0; i<=1; i++){
for(int j=0; j<=1; j++){
update(r[a]+1, c[a]+1, -1);
update(r[b]+1, c[b]+1, -1);
}
}
swap(r[a], r[b]);
swap(c[a], c[b]);
swap(grid[r[a]+1][c[a]+1], grid[r[b]+1][c[b]+1]);
for(int i=0; i<=1; i++){
for(int j=0; j<=1; j++){
update(r[a]+1, c[a]+1, 1);
update(r[b]+1, c[b]+1, 1);
}
}
return seg.query();
}
