#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/fv3/prog/debug/debug.h"
#else
#define debug(...) 42
#endif
vector<vector<int>> a;
vector<int> R, C;
int W, H, N;
bool evenSquare(int i, int x, int y) {
int sum = (int(a[R[i]+y][C[i]+x] < i) + int(a[R[i]+1+y][C[i]+x] < i) +
int(a[R[i]+1+y][C[i]+1+x] < i) + int(a[R[i]+y][C[i]+1+x] < i)) % 2;
return sum % 2 == 0;
}
struct segtree {
int nt = 1;
vector<int> mn, cnt, add;
void init() {
while (nt < N) {
nt <<= 1;
}
mn = vector<int>(2*nt, 1 << 30);
cnt = vector<int>(2*nt, 1);
add = vector<int>(2*nt);
debug(a);
debug(R);
debug(C);
mn[nt] = 4;
for (int i = 1; i < N; i++) {
mn[nt+i] = mn[nt+i-1];
if (evenSquare(i, 0, 0)) {
mn[nt+i]++;
} else {
mn[nt+i]--;
}
if (evenSquare(i, 0, -1)) {
mn[nt+i]++;
} else {
mn[nt+i]--;
}
if (evenSquare(i, -1, 0)) {
mn[nt+i]++;
} else {
mn[nt+i]--;
}
if (evenSquare(i, -1, -1)) {
mn[nt+i]++;
} else {
mn[nt+i]--;
}
}
for (int i = nt-1; i >= 1; i--) {
merge(i, i*2, i*2|1);
}
}
void prop(int k) {
mn[k] += add[k];
if (k < nt) {
add[k*2] += add[k];
add[k*2|1] += add[k];
}
add[k] = 0;
}
void update(int l, int r, int k, int tl, int tr, int val) {
prop(k);
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
add[k] += val;
prop(k);
return;
}
int c = (tl + tr) / 2;
update(l, r, k*2, tl, c, val);
update(l, r, k*2|1, c+1, tr, val);
merge(k, k*2, k*2|1);
}
void merge(int i, int c1, int c2) {
if (mn[c1] == mn[c2]) {
cnt[i] = cnt[c1] + cnt[c2];
} else if (mn[c1] < mn[c2]) {
cnt[i] = cnt[c1];
} else {
cnt[i] = cnt[c2];
}
mn[i] = min(mn[c1], mn[c2]);
}
};
segtree st;
void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_) {
W = W_; H = H_;
N = W * H;
R = R_; C = C_;
for (int i = 0; i < N; i++) {
R[i]++; C[i]++;
}
a = vector<vector<int>>(H+2, vector<int>(W+2, N));
for (int i = 0; i < N; i++) {
a[R[i]][C[i]] = i;
}
st.init();
debug(st.mn);
debug(st.cnt);
}
void updateSquare(int i, int x, int y, bool rem) {
vector<int> v = {a[R[i]+y][C[i]+x], a[R[i]+y+1][C[i]+x], a[R[i]+y][C[i]+x+1], a[R[i]+y+1][C[i]+x+1]};
sort(v.begin(), v.end());
st.update(v[0], v[1]-1, 1, 0, st.nt-1, rem ? -1 : 1);
st.update(v[2], v[3]-1, 1, 0, st.nt-1, rem ? -1 : 1);
}
int swap_seats(int u, int v) {
updateSquare(u, 0, 0, true);
updateSquare(u, -1, 0, true);
updateSquare(u, 0, -1, true);
updateSquare(u, -1, -1, true);
updateSquare(v, 0, 0, true);
updateSquare(v, -1, 0, true);
updateSquare(v, 0, -1, true);
updateSquare(v, -1, -1, true);
swap(a[R[u]][C[u]], a[R[v]][C[v]]);
swap(R[u], R[v]); swap(C[u], C[v]);
updateSquare(u, 0, 0, false);
updateSquare(u, -1, 0, false);
updateSquare(u, 0, -1, false);
updateSquare(u, -1, -1, false);
updateSquare(v, 0, 0, false);
updateSquare(v, -1, 0, false);
updateSquare(v, 0, -1, false);
updateSquare(v, -1, -1, false);
return st.cnt[1];
}
