#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<int>> g;
vector<int> r, c;
int h, w;
struct node {
int min = 0, cnt = 1, lazy = 0;
};
vector<node> seg(4000100);
void push(int v) {
seg[v<<1].min += seg[v].lazy;
seg[v<<1|1].min += seg[v].lazy;
seg[v<<1].lazy += seg[v].lazy;
seg[v<<1|1].lazy += seg[v].lazy;
seg[v].lazy = 0;
}
void update(int v, int tl, int tr, int l, int r, ll delta) {
if (l > r) return;
if (l == tl && r == tr) {
seg[v].min += delta;
seg[v].lazy += delta;
} else {
int tm = (tl+tr) >> 1;
push(v);
update(v<<1, tl, tm, l, min(r, tm), delta);
update(v<<1|1, tm+1, tr, max(l, tm+1), r, delta);
if (seg[v<<1].min == seg[v<<1|1].min) {
seg[v].min = seg[v<<1].min;
seg[v].cnt = seg[v<<1].cnt + seg[v<<1|1].cnt;
} else if (seg[v<<1].min < seg[v<<1|1].min) {
seg[v].min = seg[v<<1].min;
seg[v].cnt = seg[v<<1].cnt;
} else {
seg[v].min = seg[v<<1|1].min;
seg[v].cnt = seg[v<<1|1].cnt;
}
}
}
void process(int x, int y, int t) {
// Process the 2*2 square with top-left corner (x, y)
vector<int> cells;
for (int i=x; i<x+2; i++) {
for (int j=y; j<y+2; j++) {
if (0 <= i && i < h && 0 <= j && j < w) cells.push_back(g[i][j]);
}
}
sort(cells.begin(), cells.end());
if (cells.size() == 1) update(1, 0, h*w-1, cells[0], h*w-1, t);
else update(1, 0, h*w-1, cells[0], cells[1]-1, t);
if (cells.size() == 4) update(1, 0, h*w-1, cells[2], cells[3]-1, 5*t);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H;
w = W;
r = R;
c = C;
g = vector<vector<int>>(h, vector<int>(w));
for (int i=0; i<h*w; i++) g[R[i]][C[i]] = i;
for (int i=-1; i<h; i++) {
for (int j=-1; j<w; j++) process(i, j, 1);
}
}
int swap_seats(int a, int b) {
vector<pair<int, int>> cells;
for (int i=r[a]-1; i<=r[a]; i++) {
for (int j=c[a]-1; j<=c[a]; j++) cells.emplace_back(i, j);
}
for (int i=r[b]-1; i<=r[b]; i++) {
for (int j=c[b]-1; j<=c[b]; j++) cells.emplace_back(i, j);
}
sort(cells.begin(), cells.end());
cells.resize(unique(cells.begin(), cells.end())-cells.begin());
for (auto p : cells) process(p.first, p.second, -1);
swap(r[a], r[b]);
swap(c[a], c[b]);
swap(g[r[a]][c[a]], g[r[b]][c[b]]);
for (auto p : cells) process(p.first, p.second, 1);
return seg[1].cnt;
}
