#include <bits/stdc++.h>
#include "seats.h"
#define x first
#define y second
using namespace std;
using pii = pair<int, int>;
const int A = 1e6 + 5;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
struct Nod {
int min, cnt, lazy;
};
vector<vector<int>> mx;
vector<int> row, col;
int n, m, a;
int ql, qr, qval;
Nod pom[A * 4];
static void prop(int nod) {
pom[2 * nod + 1].lazy+= pom[nod].lazy;
pom[2 * nod].lazy+= pom[nod].lazy;
pom[nod].min+= pom[nod].lazy;
pom[nod].lazy = 0;
}
static void update(int nod, int st, int dr) {
if (qr < ql)
return;
if (ql <= st && dr <= qr) {
pom[nod].lazy+= qval;
return;
}
int mid = (st + dr) / 2;
prop(nod);
if (ql <= mid)
update(2 * nod, st, mid);
if (mid < qr)
update(2 * nod + 1, mid + 1, dr);
pom[nod].min = min(pom[2 * nod].min + pom[2 * nod].lazy, pom[2 * nod + 1].min + pom[2 * nod + 1].lazy);
pom[nod].cnt = (pom[nod].min == pom[2 * nod].min + pom[2 * nod].lazy ? pom[2 * nod].cnt : 0);
pom[nod].cnt+= (pom[nod].min == pom[2 * nod + 1].min + pom[2 * nod + 1].lazy ? pom[2 * nod + 1].cnt : 0);
}
static pii query(int nod, int st, int dr) {
if (ql <= st && dr <= qr)
return pii(pom[nod].min + pom[nod].lazy, pom[nod].cnt);
int mid = (st + dr) / 2;
pii ans = {1e9, 1e9};
prop(nod);
if (ql <= mid)
ans = query(2 * nod, st, mid);
if (mid < qr) {
pii ret = query(2 * nod + 1, mid + 1, dr);
if (ret.x < ans.x)
ans = ret;
else if (ret.x == ans.x)
ans.y+= ret.y;
}
return ans;
}
static void baga(int idx) {
vector<pii> nidx;
if (idx == a)
return;
int x = row[idx], y = col[idx];
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
int val = mx[nx][ny];
nidx.emplace_back(val, dir);
}
sort(begin(nidx), end(nidx));
ql = idx;
qr = nidx[0].x - 1;
qval = 10;
update(1, 0, a);
ql = max(idx, nidx[0].x);
qr = nidx[1].x - 1;
qval = 2;
update(1, 0, a);
if (nidx[0].y % 2 == nidx[1].y % 2)
return;
ql = max(idx, nidx[1].x);
qr = nidx[2].x - 1;
qval = 1;
update(1, 0, a);
}
static void scoate(int idx) {
vector<pii> nidx;
if (idx == a)
return;
int x = row[idx], y = col[idx];
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
int val = mx[nx][ny];
nidx.emplace_back(val, dir);
}
sort(begin(nidx), end(nidx));
ql = idx;
qr = nidx[0].x - 1;
qval = -10;
update(1, 0, a);
ql = max(idx, nidx[0].x);
qr = nidx[1].x - 1;
qval = -2;
update(1, 0, a);
if (nidx[0].y % 2 == nidx[1].y % 2)
return;
ql = max(idx, nidx[1].x);
qr = nidx[2].x - 1;
qval = -1;
update(1, 0, a);
}
static void meh(int nod, int st, int dr) {
if (st == dr) {
pom[nod].cnt = 1;
return;
}
int mid = (st + dr) / 2;
meh(2 * nod, st, mid);
meh(2 * nod + 1, mid + 1, dr);
pom[nod].cnt = dr - st + 1;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
swap(row, R);
swap(col, C);
n = H;
m = W;
a = n * m;
mx = vector<vector<int>>(n + 5, vector<int>(m + 5));
for (int i = 0; i < a; ++i)
mx[++row[i]][++col[i]] = i;
for (int i = 0; i <= n + 1; ++i)
mx[i][0] = mx[i][m + 1] = a;
for (int j = 0; j <= m + 1; ++j)
mx[0][j] = mx[n + 1][j] = a;
meh(1, 0, a);
for (int i = 0; i < a; ++i)
baga(i);
}
int swap_seats(int u, int v) {
int xu = row[u], yu = col[u];
int xv = row[v], yv = col[v];
scoate(u);
scoate(v);
for (int dir = 0; dir < 4; ++dir) {
int nx = xu + dx[dir];
int ny = yu + dy[dir];
scoate(mx[nx][ny]);
}
for (int dir = 0; dir < 4; ++dir) {
int nx = xv + dx[dir];
int ny = yv + dy[dir];
scoate(mx[nx][ny]);
}
swap(mx[xu][yu], mx[xv][yv]);
swap(col[u], col[v]);
swap(row[u], row[v]);
baga(u);
baga(v);
for (int dir = 0; dir < 4; ++dir) {
int nx = xu + dx[dir];
int ny = yu + dy[dir];
baga(mx[nx][ny]);
}
for (int dir = 0; dir < 4; ++dir) {
int nx = xv + dx[dir];
int ny = yv + dy[dir];
baga(mx[nx][ny]);
}
ql = 1, qr = a - 1;
return 1 + query(1, 0, a).y;
}
