#include <bits/stdc++.h>
#include "seats.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
#define md ((l + r) >> 1)
const int N = 1'000'005, inf = 1e9;
struct node {
array<int, 2> mn;
array<int, 2> lazy;
int cnt;
node() {
mn = {0, 0};
lazy = {0, 0};
cnt = 0;
}
node(array<int, 2> v) {
mn = v;
lazy = {0, 0};
cnt = 1;
}
friend node operator+(const node &l, const node &r) {
node ret = l;
if (r.mn < ret.mn) {
ret = r;
} else if (r.mn == l.mn) {
ret.cnt += r.cnt;
}
return ret;
}
} seg[1 << 21];
void build(int i, int l, int r) {
if (l == r) {
seg[i] = (array<int, 2>) {0, 0};
return;
}
build(i << 1, l, md);
build(i << 1 | 1, md + 1, r);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void process(int i, int l, int r) {
if (l != r) {
for (auto c : {i << 1, i << 1 | 1}) {
seg[c].lazy[0] += seg[i].lazy[0];
seg[c].lazy[1] += seg[i].lazy[1];
}
}
seg[i].mn[0] += seg[i].lazy[0];
seg[i].mn[1] += seg[i].lazy[1];
seg[i].lazy = {0, 0};
// cout << "> " << i << ' ' << seg[i].mn[0] << ' ' << seg[i].mn[1] << '\n';
}
void upd(int i, int l, int r, int s, int e, array<int, 2> v) {
process(i, l, r);
if (s <= l && r <= e) {
// cout << v[0] << ' ' << v[1] << '\n';
seg[i].lazy[0] += v[0];
seg[i].lazy[1] += v[1];
process(i, l, r);
return;
}
if (r < s || e < l) {
return;
}
upd(i << 1, l, md, s, e, v);
upd(i << 1 | 1, md + 1, r, s, e, v);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
int n, m;
vector<int> r, c;
vector<vector<int>> t;
int get(int i, int j) {
if (i < 0 || i == n || j < 0 || j == m) {
return n * m;
}
return t[i][j];
}
void process(vector<array<int, 2>> pos, int coeff) {
for (auto [x, y] : pos) {
vector<int> v;
for (int i = x; i <= x + 1; i++) {
for (int j = y; j <= y + 1; j++) {
v.push_back(get(i, j));
}
}
sort(v.begin(), v.end());
// cout << v[0] << ' ' << v[1] << ' ' << v[2] << ' ' << v[3] << '\n';
upd(1, 0, n * m - 1, v[0], v[1] - 1, {coeff, 0});
upd(1, 0, n * m - 1, v[2], v[3] - 1, {0, coeff});
}
}
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
n = _n, m = _m;
r = _r, c = _c;
t.resize(n);
for (int i = 0; i < n; i++) {
t[i].resize(m);
}
for (int i = 0; i < n * m; i++) {
t[r[i]][c[i]] = i;
}
vector<array<int, 2>> v;
for (int i = -1; i < n; i++) {
for (int j = -1; j < m; j++) {
v.push_back({i, j});
}
}
build(1, 0, n * m - 1);
process(v, 1);
}
int di[4] = {-1, 0, -1, 0};
int dj[4] = {0, -1, -1, 0};
int swap_seats(int x, int y) {
if (x > y) swap(x, y);
vector<array<int, 2>> v;
for (auto p : {x, y}) {
for (int k = 0; k < 4; k++) {
int i = r[p] + di[k], j = c[p] + dj[k];
v.push_back({i, j});
}
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
process(v, -1);
swap(r[x], r[y]);
swap(c[x], c[y]);
t[r[x]][c[x]] = x;
t[r[y]][c[y]] = y;
process(v, 1);
node val = seg[1];
// cout << val.mn[0] << ' ' << val.mn[1] << '\n';
return val.cnt;
}
