#include "seats.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
#include <limits>
#include <iterator>
namespace kod {
using std::cerr;
using std::endl;
using std::vector;
using std::pair;
using std::begin;
using std::end;
constexpr int inf = std::numeric_limits<int>::max() / 2;
struct info {
int min, count;
static info id() { return {inf, 0}; }
};
class lazy_segtree {
public:
lazy_segtree() = default;
explicit lazy_segtree(const int n) {
logn = 0;
while ((1 << logn) < n) logn += 1;
size = 1 << logn;
data.resize(2 * size, info::id());
lazy.resize(size);
for (int i = 0; i < n; ++i) {
data[i + size] = {0, 1};
}
for (int i = size - 1; i > 0; --i) {
fetch(i);
}
}
void add(int l, int r, const int x) {
l += size;
r += size;
push(l);
push(r);
const int lc = l;
const int rc = r;
while (l < r) {
if (l & 1) apply(l++, x);
if (r & 1) apply(--r, x);
l >>= 1;
r >>= 1;
}
pull(lc);
pull(rc);
}
info get() const {
return data[1];
}
private:
int size, logn;
vector<info> data;
vector<int> lazy;
void apply(const int i, const int e) {
data[i].min += e;
if (i < size) lazy[i] += e;
}
void fetch(const int i) {
const auto& l = data[2 * i + 0];
const auto& r = data[2 * i + 1];
const int m = std::min(l.min, r.min);
data[i].min = m;
data[i].count = (m == l.min ? l.count : 0) + (m == r.min ? r.count : 0);
}
void flush(const int i) {
apply(2 * i + 0, lazy[i]);
apply(2 * i + 1, lazy[i]);
lazy[i] = 0;
}
void push(const int i) {
const int lsb = __builtin_ctz(i);
for (int d = logn; d > lsb; --d) {
flush(i >> d);
}
}
void pull(int i) {
i >>= __builtin_ctz(i);
while (i > 1) fetch(i >>= 1);
}
};
int N, H, W;
vector<int> id, grid;
lazy_segtree seg;
void update(const int x, const int c) {
vector<int> list;
for (const int a : {0, 1}) {
for (const int b : {0, W}) {
list.push_back(grid[x + a + b]);
}
}
std::sort(begin(list), end(list));
seg.add(list[0], list[1], c);
seg.add(list[2], list[3], c);
}
void init() {
grid.resize(H * W, N);
for (int i = 0; i < N; ++i) {
grid[id[i]] = i;
}
seg = lazy_segtree(N);
for (int i = 0; i < H - 1; ++i) {
for (int j = 0; j < W - 1; ++j) {
update(i * W + j, 1);
}
}
}
void cell(const int x, const int a) {
for (const int a : {0, 1}) {
for (const int b : {0, W}) {
update(x - a - b, -1);
}
}
grid[x] = a;
id[a] = x;
for (const int a : {0, 1}) {
for (const int b : {0, W}) {
update(x - a - b, 1);
}
}
}
int swap(const int a, const int b) {
const int x = id[a];
const int y = id[b];
cell(x, b);
cell(y, a);
const auto ret = seg.get();
return ret.min == 4 ? ret.count : 0;
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
kod::N = H * W;
kod::H = H + 2;
kod::W = W + 2;
kod::id.resize(H * W);
for (int i = 0; i < H * W; ++i) {
kod::id[i] = (R[i] + 1) * (W + 2) + (C[i] + 1);
}
kod::init();
}
int swap_seats(int a, int b) {
return kod::swap(a, b);
}
