#include <bits/stdc++.h>
#include "seats.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 1000000
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
vp t(4 * MAXN + 1);
int lazy[4 * MAXN + 1];
pii merge(pii a, pii b) {
if (a.F > b.F) return b;
if (a.F < b.F) return a;
return {a.F, a.S + b.S};
}
void build(int v, int tl, int tr) {
if (tl == tr) t[v] = {0, 1};
else {
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
}
void push(int v) {
if (lazy[v] != 0) {
t[v * 2].F += lazy[v];
t[v * 2 + 1].F += lazy[v];
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
}
void up(int v, int tl, int tr, int l, int r, int delta) {
if (l > r) return;
if (tl == l && tr == r) {
t[v].F += delta;
lazy[v] += delta;
} else {
push(v);
int tm = (tl + tr) / 2;
up(v * 2, tl, tm, l, min(r, tm), delta);
up(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, delta);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
}
vvi arr;
vvb seen;
int n, H, W;
void add(int x, int y, int t) {
vi v = {arr[x][y], arr[x + 1][y], arr[x][y + 1], arr[x + 1][y + 1]};
sort(v.begin(), v.end());
up(1, 1, n, v[0], min(n, v[1] - 1), t);
up(1, 1, n, v[2], min(n, v[3] - 1), t);
}
vi R, C;
void give_initial_chart(int h, int w, vi r, vi c) {
R = r;
C = c;
H = h;
W = w;
n = H * W;
build(1, 1, n);
arr.resize(H + 2, vi(W + 2, 0));
seen.resize(H + 2, vb(W + 2, false));
for (int i = 0; i < n; i++) arr[R[i] + 1][C[i] + 1] = i + 1;
for (int i = 0; i <= W + 1; i++) arr[0][i] = arr[H + 1][i] = INF;
for (int i = 0; i <= H + 1; i++) arr[i][0] = arr[i][W + 1] = INF;
for (int i = 0; i <= H; i++)
for (int j = 0; j <= W; j++)
add(i, j, 1);
}
int swap_seats(int a, int b) {
vp cur = {
{R[a] + 1, C[a] + 1}, {R[a], C[a] + 1}, {R[a] + 1, C[a]},
{R[a], C[a]}, {R[b] + 1, C[b] + 1}, {R[b] + 1, C[b]},
{R[b], C[b] + 1}, {R[b], C[b]}
};
for (auto &[x, y] : cur) {
if (!seen[x][y]) add(x, y, -1);
seen[x][y] = true;
}
for (auto &[x, y] : cur) seen[x][y] = false;
swap(arr[R[a] + 1][C[a] + 1], arr[R[b] + 1][C[b] + 1]);
swap(R[a], R[b]);
swap(C[a], C[b]);
for (auto &[x, y] : cur) {
if (!seen[x][y]) add(x, y, 1);
seen[x][y] = true;
}
for (auto &[x, y] : cur) seen[x][y] = false;
return t[1].S;
}
