#include "seats.h"
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 1e6 + 5;
int n, m, pot = 1;
ii pos[maxn];
vector<vector<int>> mat;
int L[maxn * 4];
ii T[maxn * 4];
ii merge(ii A, ii B) {
if(A.x < B.x) return A;
if(A.x > B.x) return B;
return {A.x, A.y + B.y};
}
void prop(int x) {
if(L[x] == 0) return;
T[x].x += L[x];
if(x < pot)
L[x * 2] += L[x], L[x * 2 + 1] += L[x];
L[x] = 0;
}
void add_range(int x, int lo, int hi, int a, int b, int v) {
prop(x);
if(hi < a || b < lo) return;
if(a <= lo && hi <= b) {
L[x] += v;
prop(x);
return;
}
int mid = (lo + hi) / 2;
add_range(x * 2, lo, mid, a, b, v);
add_range(x * 2 + 1, mid + 1, hi, a, b, v);
T[x] = merge(T[x * 2], T[x * 2 + 1]);
}
int answer() {
if(T[1].x > 4) exit(1);
return T[1].y;
}
int check(int x, int y) {return (x >= 0) & (x < n) & (y >= 0) & (y < m);}
void update(int x, int y, int val) {
vector<int> v;
if(check(x, y)) v.pb(mat[x][y]);
if(check(x, y + 1)) v.pb(mat[x][y + 1]);
if(check(x + 1, y)) v.pb(mat[x + 1][y]);
if(check(x + 1, y + 1)) v.pb(mat[x + 1][y + 1]);
v.pb(n * m);
sort(all(v));
add_range(1, 0, pot - 1, v[0], v[1] - 1, 1 * val);
if(v.size() >= 4)
add_range(1, 0, pot - 1, v[2], v[3] - 1, 3 * val);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H, m = W;
while(pot < (n * m)) pot <<= 1;
for(int i = 0;i < n * m;i++) T[i + pot].y = 1;
for(int i = n * m;i < (pot << 1);i++) T[i + pot].x = 1e9;
for(int i = pot - 1;i > 0;i--) T[i] = merge(T[i * 2], T[i * 2 + 1]);
for(int i = 0;i < n;i++)
mat.pb(vector<int>(m, 0));
for(int i = 0;i < n * m;i++)
mat[R[i]][C[i]] = i, pos[i] = {R[i], C[i]};
for(int i = -1;i < n;i++)
for(int j = -1;j < m;j++)
update(i, j, 1);
}
int swap_seats(int a, int b) {
set<ii> s;
for(int i = 0;i < 2;i++)
for(int j = 0;j < 2;j++) {
s.insert({pos[a].x - i, pos[a].y - j});
s.insert({pos[b].x - i, pos[b].y - j});
}
for(ii p : s) update(p.x, p.y, -1);
swap(mat[pos[a].x][pos[a].y], mat[pos[b].x][pos[b].y]);
swap(pos[a], pos[b]);
for(ii p : s) update(p.x, p.y, +1);
return answer();
}
