#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include "seats.h"
//#define int long long
#define ll int
#define ull unsigned long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r) {
return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const int inf = 1e9;
const int mod2 = 1e9 + 7;
//const ll base=67;
const double lim = 0.9;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,
r2, center;
ll i, s10, s12, k1, k2, k3, s11, w, l, r, dem5, dem6, dem7, dem9, root, q;
ll el = 19;
vector<vector<int>>a;
int b[1000001], c[1000001];
struct segtree {
int cnt[4000001];
int t[4000001], lazy[4000001];
void build(int node, int l, int r) {
cnt[node] = r - l + 1;
if (l == r)
return;
int mid = l + r >> 1;
build(node << 1, l, mid);
build(node << 1 | 1, mid + 1, r);
}
void upd(int node, int l, int r, int l1, int r1, int x) {
if (l > r1 || r < l1)
return;
if (l >= l1 && r <= r1) {
lazy[node] += x;
t[node] += x;
return;
}
int mid = l + r >> 1;
upd(node << 1, l, mid, l1, r1, x);
upd(node << 1 | 1, mid + 1, r, l1, r1, x);
t[node] = min(t[node << 1], t[node << 1 | 1]);
cnt[node] = (t[node << 1] == t[node]) * cnt[node << 1] + (t[node << 1 | 1] == t[node]) * cnt[node << 1 | 1];
t[node] += lazy[node];
}
} st;
void add(int x, int y, int z) {
st.upd(1, 1, n * m, x, y, z);
}
void upd(int x, int y, int z) {
vector<int> val;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
if (x + i <= n && y + j <= m && x + i > 0 && y + j > 0)
val.pb(a[x + i][y + j]);
sort(val.begin(), val.end());
if (val.size() == 4) {
add(val[2], val[3] - 1, 5 * z);
}
val.pb(n * m + 1);
add(val[0], val[1] - 1, z);
}
struct ib {
int a, b;
bool operator==(const ib &other) const {
return a == other.a && b == other.b;
}
};
vector<ib> vc;
bool cmp(ib a, ib b) {
if (a.a == b.a)
return a.b < b.b;
return a.a < b.a;
}
void buff(int x, int y) {
for (int i = -1; i <= 0; i++)
for (int j = -1; j <= 0; j++)
vc.pb({x + i, y + j});
}
void give_initial_chart(int H, int W, vector<int>R, vector<int> C) {
n = H;
m = W;
a.resize(n + 1, vector<int>(m + 1));
st.build(1, 1, n * m);
for (int i = 0; i < R.size(); i++)
a[R[i] + 1][C[i] + 1] = i + 1, b[i + 1] = R[i] + 1, c[i + 1] = C[i] + 1;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
upd(i, j, 1);
}
int swap_seats(int x, int y) {
x++;
y++;
l = b[x];
r = c[x];
s2 = b[y];
s3 = c[y];
vc.clear();
buff(l, r);
buff(s2, s3);
swap(b[x],b[y]);
swap(c[x],c[y]);
sort(vc.begin(), vc.end(), cmp);
vc.erase(unique(vc.begin(), vc.end()), vc.end());
for (auto x : vc)
upd(x.a, x.b, -1);
swap(a[l][r], a[s2][s3]);
for (auto x : vc)
upd(x.a, x.b, 1);
return st.cnt[1];
}
