#include "seats.h"
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
#define pb push_back
#define S second
#define F first
typedef pair<int, int> pii;
const int N = 1e6 + 200;
const int inf = (1 << 30);
const int dx[] = {0, -1, 0, -1};
const int dy[] = {0, 0, -1, -1};
int S, ans = 0;
int H, W;
int cur[4];
int **val, **was;
pii pos[N];
struct tree_line {
int t[N << 2], p[N << 2];
int cnt[N << 2];
inline void push(int v, int tl, int tr) {
if (p[v] != 0) {
if (tl != tr) {
p[v * 2] += p[v];
p[v * 2 + 1] += p[v];
}
t[v] += p[v];
p[v] = 0;
}
}
void build(int v = 1, int tl = 1, int tr = S) {
cnt[v] = tr - tl + 1;
if (tl == tr) return;
int tm = tl + tr >> 1;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
}
void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = S) {
push(v, tl, tr);
if (r < tl || tr < l || l > r)
return;
if (l <= tl && tr <= r) {
p[v] += val;
push(v, tl, tr);
return;
}
int tm = tl + tr >> 1;
upd(l, r, val, v * 2, tl, tm);
upd(l, r, val, v * 2 + 1, tm + 1, tr);
t[v] = min(t[v * 2], t[v * 2 + 1]);
cnt[v] = 0;
if (t[v] == t[v * 2])
cnt[v] += cnt[v * 2];
if (t[v] == t[v * 2 + 1])
cnt[v] += cnt[v * 2 + 1];
}
int get() {
return cnt[1];
}
} t;
void del(int _x, int _y) {
for (int j = 0, x, y; j < 4; ++j) {
x = _x - dx[j];
y = _y - dy[j];
if (was[x][y]) continue;
was[x][y] = 1;
for (int i = 0; i < 4; ++i)
cur[i] = val[x + dx[i]][y + dy[i]];
if (cur[0] > cur[1]) swap(cur[0], cur[1]);
if (cur[1] > cur[2]) swap(cur[1], cur[2]);
if (cur[0] > cur[1]) swap(cur[0], cur[1]);
if (cur[2] > cur[3]) swap(cur[2], cur[3]);
if (cur[1] > cur[2]) swap(cur[1], cur[2]);
if (cur[0] > cur[1]) swap(cur[0], cur[1]);
t.upd(cur[0], cur[1] - 1, -1);
t.upd(cur[2], cur[3] - 1, -5);
}
}
void add(int _x, int _y) {
for (int j = 0, x, y; j < 4; ++j) {
x = _x - dx[j];
y = _y - dy[j];
if (was[x][y]) continue;
was[x][y] = 1;
for (int i = 0; i < 4; ++i)
cur[i] = val[x + dx[i]][y + dy[i]];
if (cur[0] > cur[1]) swap(cur[0], cur[1]);
if (cur[1] > cur[2]) swap(cur[1], cur[2]);
if (cur[0] > cur[1]) swap(cur[0], cur[1]);
if (cur[2] > cur[3]) swap(cur[2], cur[3]);
if (cur[1] > cur[2]) swap(cur[1], cur[2]);
if (cur[0] > cur[1]) swap(cur[0], cur[1]);
t.upd(cur[0], cur[1] - 1, +1);
t.upd(cur[2], cur[3] - 1, +5);
}
}
void clr(int _x, int _y) {
for (int j = 0, x, y; j < 4; ++j) {
x = _x - dx[j];
y = _y - dy[j];
was[x][y] = 0;
}
}
void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
H = _H, W = _W;
S = H * W;
val = new int*[H + 5];
was = new int*[H + 5];
for (int i = 0; i <= H + 3; ++i) {
val[i] = new int[W + 5];
was[i] = new int[W + 5];
}
for (int i = 1; i <= S; ++i) {
C[i - 1]++, R[i - 1]++;
pos[i] = {R[i - 1], C[i - 1]};
val[R[i - 1]][C[i - 1]] = i;
}
t.build();
for (int i = 0; i <= W + 1; ++i)
val[0][i] = val[H + 1][i] = S + 1;
for (int i = 0; i <= H + 1; ++i)
val[i][0] = val[i][W + 1] = S + 1;
for (int i = 1; i <= H + 1; ++i) {
for (int j = 1; j <= W + 1; ++j) {
for (int k = 0; k < 4; ++k)
cur[k] = val[i + dx[k]][j + dy[k]];
if (cur[0] > cur[1]) swap(cur[0], cur[1]);
if (cur[1] > cur[2]) swap(cur[1], cur[2]);
if (cur[0] > cur[1]) swap(cur[0], cur[1]);
if (cur[2] > cur[3]) swap(cur[2], cur[3]);
if (cur[1] > cur[2]) swap(cur[1], cur[2]);
if (cur[0] > cur[1]) swap(cur[0], cur[1]);
t.upd(cur[0], cur[1] - 1, +1);
t.upd(cur[2], cur[3] - 1, +5);
}
}
return;
}
int swap_seats(int a, int b) {
++a, ++b;
del(pos[a].F, pos[a].S);
del(pos[b].F, pos[b].S);
clr(pos[a].F, pos[a].S);
clr(pos[b].F, pos[b].S);
swap(pos[a], pos[b]);
val[pos[a].F][pos[a].S] = a;
val[pos[b].F][pos[b].S] = b;
add(pos[a].F, pos[a].S);
add(pos[b].F, pos[b].S);
clr(pos[a].F, pos[a].S);
clr(pos[b].F, pos[b].S);
return t.get();
}
