#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e6 + 5;
const int inf = 0x3f3f3f3f;

struct Data
{
	int mn,cnt;
};
Data operator + (Data A,Data B)
{
	if(A.mn < B.mn) return A;
	if(A.mn > B.mn) return B;
	return Data{A.mn, A.cnt + B.cnt};
}

struct Segment_Tree
{
	Data tree[MAXN<<2];
	int tag[MAXN<<2];
	#define ls(u) ((u)<<1)
	#define rs(u) ((u)<<1|1)
	#define lson(u) ls(u),l,mid
	#define rson(u) rs(u),mid+1,r
	void push_up(int u)
	{
		tree[u] = tree[ls(u)] + tree[rs(u)];
	}
	void upd(int u,int k)
	{
		tree[u].mn += k;
		tag[u] += k;
	}
	void push_down(int u)
	{
		if(tag[u])
		{
			upd(ls(u), tag[u]);
			upd(rs(u), tag[u]);
			tag[u] = 0;
		}
	}
	void build(int u,int l,int r)
	{
		tree[u] = {0, r-l+1};
		if(l == r) return;
		int mid = (l+r)>>1;
		build(lson(u)); build(rson(u));
	}
	void add(int u,int l,int r,int ql,int qr,int k)
	{
		if(ql<=l && r<=qr){ upd(u,k); return;}
		push_down(u);
		int mid = (l+r)>>1;
		if(ql<=mid) add(lson(u),ql,qr,k);
		if(mid<qr) add(rson(u),ql,qr,k);
		push_up(u);
	}
}tree;

int H, W, n;
array<int,2> p[MAXN];
vector< vector<int> > id;

void upd(int x,int y,int k)
{
	vector<int> vec = {id[x][y], id[x-1][y], id[x][y-1], id[x-1][y-1]};
	sort(vec.begin(), vec.end());
	
	tree.add(1,1,n, vec[0], min(vec[1]-1, n), k);
	
	if(vec[3]-1 <= n)
		tree.add(1,1,n, vec[2], vec[3]-1, k);
}

void give_initial_chart(int _H, int _W, vector<int> xs, vector<int> ys)
{
	H = _H; W = _W;
	n = H * W;
	id.resize(H+2, vector<int>(W+2, inf));
	for(int i=1; i<=n; ++i)
	{
		p[i] = {xs[i-1] + 1, ys[i-1] + 1};
		id[p[i][0]][p[i][1]] = i;
	}
	
	tree.build(1,1,n);
	for(int i=1; i<=H+1; ++i)
		for(int j=1; j<=W+1; ++j)
			upd(i, j, 1);
}

int swap_seats(int i, int j)
{
	++i; ++j;
	
	int xi = p[i][0], yi = p[i][1];
	int xj = p[j][0], yj = p[j][1];
	vector<pii> pos = {{xi, yi}, {xi+1, yi}, {xi, yi+1}, {xi+1, yi+1},
	                   {xj, yj}, {xj+1, yj}, {xj, yj+1}, {xj+1, yj+1}};
	sort(pos.begin(), pos.end());
	pos.erase(unique(pos.begin(), pos.end()), pos.end());
	
	for(auto t: pos)
		upd(t.first, t.second, -1);
	
	swap(p[i], p[j]);
	swap(id[xi][yi], id[xj][yj]);
	
	for(auto t: pos)
		upd(t.first, t.second, 1);
	
	auto res = tree.tree[1];
	return res.mn == 4? res.cnt: 0;
}