#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include "seats.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e6+5;
int n, m;
int tot;
int r[maxn];
struct node
{
int val, cnt, lz;
node(int a = 0, int b = 0) : val(a), cnt(b)
{
lz = 0;
}
};
node st[4*maxn];
node pull(node &x, node &y)
{
if(x.val< y.val) return x;
if(x.val> y.val) return y;
return node(x.val, x.cnt+y.cnt);
}
void pushdown(int p, int L, int R)
{
if(st[p].lz == 0) return;
st[p].val += st[p].lz;
if(L != R)
{
st[2*p].lz += st[p].lz;
st[2*p+1].lz += st[p].lz;
}
st[p].lz = 0;
}
void build(int p = 1, int L = 0, int R = tot-1)
{
if(L == R)
{
st[p] = node(0, 1);
return;
}
int M = (L+R)/2;
build(2*p, L, M);
build(2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
void update(int i, int j, int dx, int p = 1, int L = 0, int R = tot-1)
{
pushdown(p, L, R);
if(i> j || i> R || j< L) return;
if(i<= L && R<= j)
{
st[p].lz += dx;
pushdown(p, L, R);
return;
}
int M = (L+R)/2;
update(i, j, dx, 2*p, L, M);
update(i, j, dx, 2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
node ask(int i, int j, int p = 1, int L = 0, int R = tot-1)
{
if(i> R || j< L) return node(1e9, 0);
pushdown(p, L, R);
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
node x = ask(i, j, 2*p, L, M);
node y = ask(i, j, 2*p+1, M+1, R);
return pull(x, y);
}
vector< vector<int> > bow;
int row[maxn];
int col[maxn];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
void add(int x, int y, int a, int b)
{
// printf("add %d to [%d %d]\n", val, a, b);
for(int base = 0; base< 8; base += 2)
{
vector<int> t;
for(int pp = base; pp<= base+2; pp++)
{
int pos = pp%8;
// printf("%d ", pos);
int loc = 1e9;
if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
{
loc = bow[x+dx[pos]][y+dy[pos]];
}
t.pb(loc);
}
// printf("\n");
sort(t.begin(), t.end());
int t0 = t[0], t1 = t[1], t2 = t[2];
// printf("%d %d %d\n", t0, t1, t2);
update(a, min(t0-1, b), 1);
update(max(a, t0), min(t1-1, b), -1);
update(max(a, t1), min(t2-1, b), 1);
update(max(a, t2), b, -1);
}
}
void rem(int x, int y, int a, int b)
{
for(int base = 0; base< 8; base += 2)
{
vector<int> t;
for(int pp = base; pp<= base+2; pp++)
{
int pos = pp%8;
int loc = 1e9;
if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
{
loc = bow[x+dx[pos]][y+dy[pos]];
}
t.pb(loc);
}
sort(t.begin(), t.end());
int t0 = t[0], t1 = t[1], t2 = t[2];
// printf("%d %d %d\n", t0, t1, t2);
update(a, min(t0-1, b), -1);
update(max(a, t0), min(t1-1, b), 1);
update(max(a, t1), min(t2-1, b), -1);
update(max(a, t2), b, 1);
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
n = H; m = W;
tot = n*m;
bow.assign(n, vector<int>(m));
build();
int prv = 0;
for(int i = 0; i< tot; i++)
{
bow[R[i]][C[i]] = i;
row[i] = R[i];
col[i] = C[i];
}
for(int i = 0; i< tot; i++)
{
int cur = prv;
for(int base = 0; base< 8; base += 2)
{
int cnt = 0;
for(int pp = base; pp<= base+2; pp++)
{
int pos = pp%8;
int loc = 0;
int x = row[i], y = col[i];
if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
{
loc = bow[x+dx[pos]][y+dy[pos]]< i;
}
cnt += loc;
}
if(cnt == 1 || cnt == 3) cur--;
else cur++;
}
update(i, i, cur);
// printf("f[%d] = %d\n", i, cur);
prv = cur;
}
// printf("(%d, %d)\n", kk.val, kk.cnt);
}
int swap_seats(int a, int b)
{
if(a> b) swap(a, b);
rem(row[a], col[a], a, b-1);
// printf("finished reming\n");
// printf("f' = ");
// for(int i = 0; i< tot; i++) printf("%d ", ask(i, i).val);
// printf("\n");
swap(bow[row[a]][col[a]], bow[row[b]][col[b]]);
add(row[b], col[b], a, b-1);
swap(row[a], row[b]);
swap(col[a], col[b]);
node kk = ask(0, tot-1);
// printf("f = ");
// for(int i = 0; i< tot; i++) printf("%d ", ask(i, i).val);
// printf("\n");
// printf("(%d, %d)\n", kk.val, kk.cnt);
if(kk.val == 4) return kk.cnt;
return 0;
}
