#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
template<int n, typename T, typename Updater>
class LazyAint {
private:
T neutralUpd, neutralQry, initval;
T *aint;
T *lazy;
Updater upd;
int lInit, rInit;
inline void pushlazy(int nod, int l, int r) {
aint[nod] = upd.update(aint[nod], lazy[nod], r - l + 1);
if(2 * nod <= 4 * n)
lazy[2 * nod] = upd.update(lazy[2 * nod], lazy[nod], r - l + 1);
if(2 * nod + 1 <= 4 * n)
lazy[2 * nod + 1] = upd.update(lazy[2 * nod + 1], lazy[nod], r - l + 1);
lazy[nod] = neutralUpd;
}
void updateDfs(int i, int j, T val, int nod = 1, int l = 1, int r = n) {
pushlazy(nod, l, r);
if(r < i || j < l || r < l || j < i)
return ;
if(i <= l && r <= j) {
lazy[nod] = upd.update(lazy[nod], val, r - l + 1);
pushlazy(nod, l, r);
return;
}
int mid = (l + r) / 2;
if(l < r) {
updateDfs(i, j, val, 2 * nod, l, mid);
updateDfs(i, j, val, 2 * nod + 1, mid + 1, r);
aint[nod] = upd.query(aint[2 * nod], aint[2 * nod + 1]);
}
}
T queryDfs(int i, int j, int nod = 1, int l = 1, int r = n) {
if(r < i || j < l || r < l || j < i)
return neutralQry;
pushlazy(nod, l, r);
if(i <= l && r <= j)
return aint[nod];
int mid = (l + r) / 2;
return upd.query(queryDfs(i, j, 2 * nod, l, mid),
queryDfs(i, j, 2 * nod + 1, mid + 1, r));
}
void initDfs(int nod, int l, int r) {
int mid = (l + r) / 2;
if(l < r) {
initDfs(2 * nod, l, mid);
initDfs(2 * nod + 1, mid + 1, r);
aint[nod] = upd.query(aint[2 * nod], aint[2 * nod + 1]);
} else
aint[nod] = initval;
}
public:
LazyAint(T _neutralUpd, T _neutralQry, T _initval, int _lInit = 1, int _rInit = n) {
neutralUpd = _neutralUpd;
neutralQry = _neutralQry;
initval = _initval;
lInit = _lInit;
rInit = _rInit;
aint = new T[1 + 4 * n];
lazy = new T[1 + 4 * n];
for(int i = 0; i <= 4 * n; ++i)
lazy[i] = neutralUpd;
initDfs(1, lInit, rInit);
}
inline void update(int i, int j, T val) {
updateDfs(i, j, val, 1, lInit, rInit);
}
inline T query(int i, int j) {
return queryDfs(i, j, 1, lInit, rInit);
}
};
const int MAX_N = 1000000;
struct Node {
int minVal, fr;
inline Node update(Node a, Node b, int x) {
a.minVal += b.minVal;
return a;
}
inline Node query(Node a, Node b) {
if(b.minVal < a.minVal) {
a.minVal = b.minVal;
a.fr = b.fr;
} else if(b.minVal == a.minVal)
a.fr += b.fr;
return a;
}
};
LazyAint<1+MAX_N, Node, Node> aint({0, 0}, {MAX_N + 1, 0}, {0, 1}, 0, MAX_N);
int N;
int cells[4];
int **matr;
vector<int> R, C;
static inline void activateSqr(int l, int c, int x) {
cells[0] = matr[l][c];
cells[1] = matr[l + 1][c];
cells[2] = matr[l][c + 1];
cells[3] = matr[l + 1][c + 1];
std::sort(cells, cells + 4);
aint.update(cells[0], cells[1] - 1, {x, 0});
aint.update(cells[2], cells[3] - 1, {4 * x, 0});
}
static inline void activateCells(int l, int c, int x) {
activateSqr(l, c, x);
activateSqr(l - 1, c, x);
activateSqr(l, c - 1, x);
activateSqr(l - 1, c - 1, x);
}
void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
N = H * W;
R = _R;
C = _C;
matr = new int*[1 + H + 1];
for(int i = 0; i <= H + 1; ++i) {
matr[i] = new int[1 + W + 1];
for(int j = 0; j <= W + 1; ++j)
matr[i][j] = N;
}
for(int i = 0; i < N; ++i) {
R[i]++;
C[i]++;
matr[R[i]][C[i]] = i;
}
for(int i = 0; i <= H; ++i)
for(int j = 0; j <= W; ++j)
activateSqr(i, j, 1);
}
int swap_seats(int a, int b) {
activateCells(R[a], C[a], -1);
activateCells(R[b], C[b], -1);
swap(R[a], R[b]);
swap(C[a], C[b]);
swap(matr[R[a]][C[a]], matr[R[b]][C[b]]);
activateCells(R[a], C[a], 1);
activateCells(R[b], C[b], 1);
Node x = aint.query(0, N - 1);
if(x.minVal != 4)
return 0;
return x.fr;
}
