#include "seats.h"
#include <algorithm>
using namespace std;
struct SegTree {
int n;
vector<int> mn, cnt, delta;
void apply(int v, int val) {
mn[v] += val;
delta[v] += val;
}
void push(int v) {
apply(2 * v, delta[v]);
apply(2 * v + 1, delta[v]);
delta[v] = 0;
}
void pull(int v) {
mn[v] = min(mn[2 * v], mn[2 * v + 1]);
cnt[v] = (mn[2 * v] == mn[v] ? cnt[2 * v] : 0) + (mn[2 * v + 1] == mn[v] ? cnt[2 * v + 1] : 0);
}
void update(int v, int l, int r, int ql, int qr, int val) {
if (l >= qr || r <= ql)
return;
if (l >= ql && r <= qr) {
apply(v, val);
return;
}
push(v);
int mid = (l + r) / 2;
update(2 * v, l, mid, ql, qr, val);
update(2 * v + 1, mid, r, ql, qr, val);
pull(v);
}
void build(int v, int l, int r) {
if (r - l == 1) {
mn[v] = 0;
cnt[v] = 1;
} else {
int mid = (l + r) / 2;
build(2 * v, l, mid);
build(2 * v + 1, mid, r);
pull(v);
}
}
int get(int need) {
return mn[1] == need ? cnt[1] : 0;
}
SegTree() {}
SegTree(int n) : n(n) {
mn.resize(4 * n);
cnt.resize(4 * n);
delta.resize(4 * n);
build(1, 0, n);
}
};
const int N = 1e6 + 10;
int h, w, n;
int r[N], c[N];
vector<vector<int>> arr;
SegTree st;
void update(int x, int y, int delta) {
vector<int> vals;
for (int i = x; i <= x + 1; ++i) {
for (int j = y; j <= y + 1; ++j) {
vals.push_back(i >= 0 && i < h && j >= 0 && j < w ? arr[i][j] : n);
}
}
sort(vals.begin(), vals.end());
st.update(1, 0, n, vals[0], vals[1], delta);
st.update(1, 0, n, vals[2], vals[3], delta);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H, w = W;
n = h * w;
arr.resize(h, vector<int>(w));
for (int i = 0; i < h * w; ++i) {
r[i] = R[i];
c[i] = C[i];
arr[r[i]][c[i]] = i;
}
st = {n};
for (int x = -1; x < h; ++x) {
for (int y = -1; y < w; ++y) {
update(x, y, 1);
}
}
}
int swap_seats(int a, int b) {
vector<pair<int, int>> changes;
for (int i = r[a] - 1; i <= r[a]; ++i) {
for (int j = c[a] - 1; j <= c[a]; ++j) {
changes.push_back({i, j});
}
}
for (int i = r[b] - 1; i <= r[b]; ++i) {
for (int j = c[b] - 1; j <= c[b]; ++j) {
changes.push_back({i, j});
}
}
sort(changes.begin(), changes.end());
changes.resize(unique(changes.begin(), changes.end()) - changes.begin());
for (auto p : changes) {
update(p.first, p.second, -1);
}
swap(arr[r[a]][c[a]], arr[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
for (auto p : changes) {
update(p.first, p.second, 1);
}
return st.get(4);
}
