#include "seats.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
const int INF = 1e9;
int n, m;
vector<vi> T;
vi R, C;
using i4 = array<int, 4>;
const int MN = 1e6;
namespace AINT {
int n;
i4 Mi[4 * MN], Lz[4 * MN];
vi Nr;
void build(int u, int s, int d, const vi S[4]);
void init(int N, const vi S[4]) {
n = N;
Nr.assign(4 * N, 0);
for(int i = 0; i < 4 * N; ++i)
Mi[i] = Lz[i] = i4{0, 0, 0, 0};
build(1, 0, n - 1, S);
}
void build(int u, int s, int d, const vi S[4]) {
if(s != d) {
build(u << 1, s, (s + d) >> 1, S);
build(u << 1 | 1, ((s + d) >> 1) + 1, d, S);
Mi[u] = min(Mi[u << 1], Mi[u << 1 | 1]);
Nr[u] = 0;
if(Mi[u] == Mi[u << 1]) Nr[u] += Nr[u << 1];
if(Mi[u] == Mi[u << 1 | 1]) Nr[u] += Nr[u << 1 | 1];
} else {
for(int a = 0; a < 4; ++a) Mi[u][a] = S[a][s];
Nr[u] = 1;
}
}
void prop(int u, int s, int d) {
for(int a = 0; a < 4; ++a) {
Mi[u][a] += Lz[u][a];
if(s != d) {
Lz[u << 1][a] += Lz[u][a];
Lz[u << 1 | 1][a] += Lz[u][a];
}
Lz[u][a] = 0;
}
}
void update(int l, int r, i4 v, int u, int s, int d) {
prop(u, s, d);
if(d < l || r < s) return;
if(l <= s && d <= r) {
for(int a = 0; a < 4; ++a) Lz[u][a] += v[a];
prop(u, s, d);
return;
}
update(l, r, v, u << 1, s, (s + d) >> 1);
update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
Mi[u] = min(Mi[u << 1], Mi[u << 1 | 1]);
Nr[u] = 0;
if(Mi[u] == Mi[u << 1]) Nr[u] += Nr[u << 1];
if(Mi[u] == Mi[u << 1 | 1]) Nr[u] += Nr[u << 1 | 1];
}
void update(int l, int r, i4 v) {
if(l > r) return;
update(l, r, v, 1, 0, n - 1);
}
int cnt() {
if(Mi[1] == i4{1, 1, 1, 1}) return Nr[1];
return 0;
}
};
using ii4 = array<ii, 4>;
static pair<ii4, ii4> recalc_int(int i, int j) {
///va recalcula intervalele de relevanta, Lin si Pat
///0 <- (i, j)
///1
ii4 lin, pat;
lin[0] = {T[i + 1][j], T[i][j] - 1};
pat[0] = {max(T[i + 1][j], T[i + 1][j + 1]), min(T[i][j], T[i][j + 1]) - 1};
/// 1 -> dreapta (1*, 0)
lin[1] = {T[i][j], T[i][j + 1] - 1};
pat[1] = {max(T[i][j], T[i + 1][j]), min(T[i][j + 1], T[i + 1][j + 1]) - 1};
/// 2 -> jos
/// 1*
/// 0
lin[2] = {T[i][j], T[i + 1][j] - 1};
pat[2] = {max(T[i][j], T[i][j + 1]), min(T[i + 1][j], T[i + 1][j + 1]) - 1};
///3 -> stanga
/// 0* 1
lin[3] = {T[i][j + 1], T[i][j] - 1};
pat[3] = {max(T[i][j + 1], T[i + 1][j + 1]), min(T[i][j], T[i + 1][j]) - 1};
return {lin, pat};
}
int h, w;
void give_initial_chart(int H, int W, vi R0, vi C0) {
R = R0; C = C0;
n = H + 2; m = W + 2;
h = H; w = W;
T.resize(n, vi(m, INF));
for(int i = 0; i < R.size(); ++i) {
T[R[i] + 1][C[i] + 1] = i;
}
vi S[4];
for(int a = 0; a < 4; ++a) S[a].resize(h * w, 0);
for(int i = 0; i <= H; ++i)
for(int j = 0; j <= W; ++j) {
auto [LV, PV] = recalc_int(i, j);
for(int d = 0; d < 4; ++d) {
auto [l1, r1] = LV[d];
//add(l1, r1, d, 1);
if(l1 <= r1) {
S[d][l1]++;
if(r1 + 1 < h * w) -- S[d][r1 + 1];
}
auto [l2, r2] = PV[d];
if(l2 <= r2) {
//add(l2, r2, d, -1);
S[d][l2]--;
if(r2 + 1 < h * w) ++S[d][r2 + 1];
}
}
}
for(int i = 1; i < h * w; ++i) {
for(int d = 0; d < 4; ++d)
S[d][i] += S[d][i - 1];
}
AINT::init(h * w, S);
}
void change(int a, int b) {
swap(T[R[a] + 1][C[a] + 1], T[R[b] + 1][C[b] + 1]);
swap(R[a], R[b]);
swap(C[a], C[b]);
}
static void reset(int l, int c, int a, int b) {
///un 3 x 3 in apropiere
auto add = [&](int l, int r, int d, int sgn) {
i4 v{0, 0, 0, 0}; v[d] = sgn;
AINT::update(l, r, v);
};
for(int i = max(0, l - 1); i <= min(n - 2, l + 1); ++i) {
for(int j = max(0, c - 1); j <= min(m - 2, c + 1); ++j) {
auto [LV, PV] = recalc_int(i, j);
change(a, b);
auto [NLV, NPV] = recalc_int(i, j);
for(int d = 0; d < 4; ++d) {
if(NLV[d] != LV[d]) {
auto [l1, r1] = LV[d];
auto [ll1, rr1] = NLV[d];
add(l1, r1, d, -1);
add(ll1, rr1, d, 1);
}
if(NPV[d] != PV[d]) {
auto [l2, r2] = PV[d];
add(l2, r2, d, 1);
auto [ll2, rr2] = NPV[d];
add(ll2, rr2, d, -1);
}
}
change(a, b);
}
}
}
int swap_seats(int a, int b) {
reset(R[a], C[a], a, b);
reset(R[b], C[b], a, b);
change(a, b);
return AINT::cnt();
}
