#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
const int INF = 1e9;
int n, m;
vector<vi> T;
vector<vector<ii> > Lin[4];
vector<vector<ii> > Pat[4];
vi R, C;
using i4 = array<int, 4>;
struct AINT {
int n;
vector<i4> Mi, Lz, V;
vi Nr;
AINT() {}
AINT(int N) : n(N), Mi(4 * N, {0, 0, 0, 0}), Lz(4 * N, {0, 0, 0, 0}), V(N, {0, 0, 0, 0}), Nr(4 * N, 0) {
build(1, 0, n - 1);
}
void build(int u, int s, int d) {
Nr[u] = d - s + 1;
if(s != d) {
build(u << 1, s, (s + d) >> 1);
build(u << 1 | 1, ((s + d) >> 1) + 1, d);
}
}
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) {
// for(int i = l; i <= min(r, n - 1); ++i) {
// for(int a = 0; a < 4; ++a)
// V[i][a] += v[a];
// }
// return;
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;
}
};
void recalc_int(int i, int j) {
///va recalcula intervalele de relevanta, Lin si Pat
///0 <- (i, j)
///1
Lin[0][i][j] = {T[i + 1][j], T[i][j] - 1};
Pat[0][i][j] = {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][i][j] = {T[i][j], T[i][j + 1] - 1};
Pat[1][i][j] = {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][i][j] = {T[i][j], T[i + 1][j] - 1};
Pat[2][i][j] = {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][i][j] = {T[i][j + 1], T[i][j] - 1};
Pat[3][i][j] = {max(T[i][j + 1], T[i + 1][j + 1]), min(T[i][j], T[i + 1][j]) - 1};
}
AINT Sol;
void give_initial_chart(int H, int W, vi R0, vi C0) {
R = R0; C = C0;
n = H + 2; m = W + 2;
T.resize(n, vi(m, INF));
Sol = AINT(W * H);
for(int d = 0; d < 4; ++d) {
Lin[d].resize(H + 1, vector<ii>(W + 1, ii{-1, 0}));
Pat[d].resize(H + 1, vector<ii>(W + 1, ii{-1, 0}));
}
for(int i = 0; i < R.size(); ++i) {
T[R[i] + 1][C[i] + 1] = i;
}
auto add = [&](int l, int r, int d, int sgn) {
i4 v{0, 0, 0, 0}; v[d] = sgn;
Sol.update(l, r, v);
};
for(int i = 0; i <= H; ++i)
for(int j = 0; j <= W; ++j) {
recalc_int(i, j);
for(int d = 0; d < 4; ++d) {
auto [l1, r1] = Lin[d][i][j];
add(l1, r1, d, 1);
auto [l2, r2] = Pat[d][i][j];
add(l2, r2, d, -1);
}
}
}
void reset(int l, int c) {
///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;
Sol.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) {
for(int d = 0; d < 4; ++d) {
auto [l1, r1] = Lin[d][i][j];
add(l1, r1, d, -1);
auto [l2, r2] = Pat[d][i][j];
add(l2, r2, d, 1);
}
recalc_int(i, j);
for(int d = 0; d < 4; ++d) {
auto [ll1, rr1] = Lin[d][i][j];
add(ll1, rr1, d, 1);
auto [ll2, rr2] = Pat[d][i][j];
add(ll2, rr2, d, -1);
}
}
}
}
int swap_seats(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]);
reset(R[a], C[a]);
reset(R[b], C[b]);
return Sol.cnt();
}
