#include "seats.h"
#include <algorithm>
#include <numeric>
using namespace std;
struct LazySegTree {
struct Item {
int mn = 4, cnt_min = 0;
Item friend operator+(Item const &lhs, Item const &rhs) {
if (lhs.mn == rhs.mn)
return {lhs.mn, lhs.cnt_min + rhs.cnt_min};
if (lhs.mn < rhs.mn) return lhs;
return rhs;
}
Item friend operator*(Item const &lhs, int r) {
return {lhs.mn + r, lhs.cnt_min};
}
};
int sz;
Item const NE{1 << 28, 0};
vector<Item> seg;
vector<int> lazy;
void upd(int l, int r, int val, int ver, int lx, int rx) {
propagate(ver, lx, rx);
if (r <= lx || rx <= l) return;
if (l <= lx && rx <= r) {
seg[ver] = seg[ver] * val;
lazy[ver] += val;
return;
}
int mx = (lx + rx) / 2;
upd(l, r, val, ver * 2 + 1, lx, mx);
upd(l, r, val, ver * 2 + 2, mx, rx);
seg[ver] = (seg[ver * 2 + 1] + seg[ver * 2 + 2]) * lazy[ver];
}
void build(vector<int> const &v, int ver, int lx, int rx) {
if (rx - lx == 1) {
if (lx < size(v)) {
seg[ver].mn = v[lx];
seg[ver].cnt_min = 1;
}
return;
}
int mx = (lx + rx) / 2;
build(v, ver * 2 + 1, lx, mx);
build(v, ver * 2 + 2, mx, rx);
seg[ver] = seg[ver * 2 + 1] + seg[ver * 2 + 2];
}
Item query(int l, int r, int ver, int lx, int rx) {
propagate(ver, lx, rx);
if (r <= lx || rx <= l) return NE;
if (l <= lx && rx <= r) return seg[ver];
int mx = (lx + rx) / 2;
Item const &L = query(l, r, ver * 2 + 1, lx, mx);
Item const &R = query(l, r, ver * 2 + 2, mx, rx);
return (L + R) * lazy[ver];
}
void propagate(int ver, int lx, int rx) {
if (rx - lx == 1) return;
for (int i : {1, 2}) {
lazy[ver * 2 + i] += lazy[ver];
seg[ver * 2 + i] = seg[ver * 2 + i] * lazy[ver];
}
lazy[ver] = 0;
}
void resize(int _n) {
sz = 1 << (32 - __builtin_clz(_n));
seg.resize(sz * 2);
lazy.resize(sz * 2);
}
int query() {
return query(0, sz, 0, 0, sz).cnt_min;
}
void upd(int l, int r, int val) {
if (r <= l) return;
upd(l, r, val, 0, 0, sz);
}
void build(vector<int> const &v) {
build(v, 0, 0, sz);
}
};
vector<vector<int>> mat;
vector<int> r, c;
LazySegTree st;
array<int, 4> getArr(int x, int y) {
array<int, 4> arr;
for (int i = 0; i < 4; ++i) {
arr[i] = mat[x - (i & 1)][y - ((i & 2) != 0)];
}
sort(begin(arr), end(arr));
return arr;
}
void add(int x, int y, int val) {
array<int, 4> const &arr = getArr(x, y);
st.upd(arr[0], arr[1], val);
st.upd(arr[2], arr[3], val);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r = move(R);
c = move(C);
transform(begin(r), end(r), begin(r), [](int x) { return x + 1; });
transform(begin(c), end(c), begin(c), [](int x) { return x + 1; });
int mx = H * W;
st.resize(mx);
mat = vector(H + 2, vector(W + 2, mx));
for (int i = 0; i < size(r); ++i) {
mat[r[i]][c[i]] = i;
}
vector<int> dif(mx + 1);
for (int i = 1; i <= H + 1; ++i) {
for (int j = 1; j <= W + 1; ++j) {
array<int, 4> const &arr = getArr(i, j);
for (int k = 0; k < 4; ++k) {
dif[arr[k]] += k % 2 ? -1 : 1;
}
}
}
dif.pop_back();
partial_sum(begin(dif), end(dif), begin(dif));
st.build(dif);
}
int swap_seats(int a, int b) {
for (int i = 0; i < 4; ++i) {
add(r[a] + (i & 1), c[a] + ((i & 2) != 0), -1);
add(r[b] + (i & 1), c[b] + ((i & 2) != 0), -1);
}
swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
for (int i = 0; i < 4; ++i) {
add(r[a] + (i & 1), c[a] + ((i & 2) != 0), 1);
add(r[b] + (i & 1), c[b] + ((i & 2) != 0), 1);
}
return st.query();
}
