#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int r[maxn], c[maxn], num[maxn], val[maxn*2], cnt[maxn*2], lazy[maxn*2], nr, nc, n;
void build(int l, int r, int vr = 0)
{
cnt[vr] = r-l+1;
if (l == r) return;
build(l, (l+r)/2, vr*2+1), build((l+r)/2+1, r, vr*2+2);
}
void update(int li, int ri, int v, int l, int r, int vr = 0)
{
if (ri < l || r < li) return;
if (li <= l && r <= ri)
{
val[vr] += v, lazy[vr] += v;
return;
}
update(li, ri, v, l, (l+r)/2, vr*2+1), update(li, ri, v, (l+r)/2+1, r, vr*2+2);
val[vr] = min(val[vr*2+1], val[vr*2+2]), cnt[vr] = 0;
if (val[vr] == val[vr*2+1]) cnt[vr] += cnt[vr*2+1];
if (val[vr] == val[vr*2+2]) cnt[vr] += cnt[vr*2+2];
val[vr] += lazy[vr];
}
int id(int x, int y)
{
if (x < 0 || y < 0 || x >= nr || y >= nc) return nr*nc;
return nc*x + y;
}
void change2x2(int x, int y, int d)
{
array<int, 4> a;
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) a[i*2+j] = num[id(x+i, y+j)];
sort(a.begin(), a.end());
for (int i = 0; i < 2; i++) if (a[i*2] < a[i*2+1]) update(a[i*2], a[i*2+1]-1, d, 0, n-1);
}
void change(int x, int y, int v)
{
for (int i = -1; i < 1; i++) for (int j = -1; j < 1; j++) change2x2(x+i, y+j, -1);
num[x*nc+y] = v;
for (int i = -1; i < 1; i++) for (int j = -1; j < 1; j++) change2x2(x+i, y+j, 1);
}
void give_initial_chart(int NR, int NC, vector<int> R, vector<int> C) {
nr = NR, nc = NC, n = nr * nc;
for (int i = 0; i < n; i++)
{
r[i] = R[i], c[i] = C[i];
num[r[i]*nc+c[i]] = i;
} num[nr*nc] = n;
for (int i = -1; i < nr; i++) for (int j = -1; j < nc; j++) change2x2(i, j, 1);
build(0, n-1);
}
int swap_seats(int a, int b) {
change(r[a], c[a], b);
change(r[b], c[b], a);
swap(r[a], r[b]), swap(c[a], c[b]);
return cnt[0];
}
