// Be name khode //
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int maxn = 1e6 + 5;
const int maxnt = 4e6 + 30;
const int lg = 20;
std::vector<int> r;
int n, m, have = 0, sgn, av[5];
pair <int, int> a[maxn];
vector <int> ind[maxn], st[maxn];
vector <pair<int, int>> adj = {{0, 0}, {-1, 0}, {0, -1}, {-1, -1}};
vector <pair<int, int>> sq = {{0, 0}, {1, 0}, {0, 1}, {1, 1}};
namespace seg{
int lazy[maxnt];
pair <int, int> mn[maxnt];
void upd(int l, int r, int lq, int rq, int val, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
lazy[v] += val;
mn[v].fi += val;
return;
}
int mid = (l + r) >> 1;
upd(l, mid, lq, rq, val, v * 2);
upd(mid, r, lq, rq, val, v * 2 + 1);
mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
if(mn[v * 2].fi == mn[v * 2 + 1].fi)
mn[v].se = mn[v * 2].se + mn[v * 2 + 1].se;
mn[v].fi += lazy[v];
}
void build(int l, int r, int v){
mn[v].se = r - l;
if(r - l == 1)
return;
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
}
}
bool ok(int x, int y){
return min(x, y) >= 0 && x + 1 < n && y + 1 < m;
}
void upd(int x, int y, int val){
if(st[x][y] == val)
return;
st[x][y] = val;
int pt = 0;
for(auto [u, v] : sq){
//cout << x << ' ' << y << ' ' << u << ' ' << v << ' ' << x
int w = ind[x + u][y + v];
av[pt++] = w;
//cout << "ha? " << x << ' ' << y << ' ' << u << ' ' << v << ' ' << w << endl;
}
sort(av, av + pt);
//cout << "upd of " << x << ' ' << y << ' ' << val << endl;
seg::upd(0, sgn, av[0], av[1], val, 1);
seg::upd(0, sgn, av[2], av[3], val, 1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H;
m = W;
sgn = n * m;
seg::build(0, sgn, 1);
for(int i = 0; i < n + 2; i++){
ind[i].resize(m + 2);
st[i].resize(m + 2, -1);
for(int j = 0; j < m + 2; j++)
ind[i][j] = n * m;
}
for(int i = 0; i < n * m; i++){
a[i] = {R[i] + 1, C[i] + 1};
ind[R[i] + 1][C[i] + 1] = i;
}
n += 2;
m += 2;
for(int i = 0; i < n - 1; i++)
for(int j = 0; j < m - 1; j++)
upd(i, j, 1);
}
int swap_seats(int x, int y) {
for(auto [u, v] : adj){
if(ok(a[x].fi + u, a[x].se + v))
upd(a[x].fi + u, a[x].se + v, -1);
if(ok(a[y].fi + u, a[y].se + v))
upd(a[y].fi + u, a[y].se + v, -1);
}
swap(a[x], a[y]);
ind[a[x].fi][a[x].se] = x;
ind[a[y].fi][a[y].se] = y;
for(auto [u, v] : adj){
if(ok(a[x].fi + u, a[x].se + v))
upd(a[x].fi + u, a[x].se + v, 1);
if(ok(a[y].fi + u, a[y].se + v))
upd(a[y].fi + u, a[y].se + v, 1);
}
assert(seg::mn[1].fi >= 4);
//cout << "now " << x << ' ' << y << ' ' << seg::mn[1].fi << ' ' << seg::mn[1].se << endl;
return seg::mn[1].se;
}
