#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define set owo
//segment tree base
struct segtree {
int l, r;
segtree* lc, * rc;
segtree* getmem();
int mn = 0, mncnt;
int lz = 0;
segtree() : segtree(-1, -1) {};
segtree(int l, int r) : l(l), r(r), mncnt(r - l + 1) {
if (l == r) return;
int m = (l + r) / 2;
lc = getmem(); *lc = segtree(l, m);
rc = getmem(); *rc = segtree(m + 1, r);
}
void apply(int x) {
lz += x; mn += x;
}
void push() {
if (l == r) return;
lc->apply(lz); rc->apply(lz);
lz = 0;
}
void pull() {
mn = min(lc->mn, rc->mn); mncnt = 0;
if (lc->mn == mn) mncnt += lc->mncnt;
if (rc->mn == mn) mncnt += rc->mncnt;
}
void upd(int ql, int qr, int qv) {
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) {
apply(qv);
return;
}
push();
lc->upd(ql, qr, qv);
rc->upd(ql, qr, qv);
pull();
}
//debugging only
int q(int v, int ad = 0) {
ad += lz;
if (l == r) return ad;
if (v <= lc->r) return lc->q(v, ad);
return rc->q(v, ad);
}
}uwu, mem[4000005];
int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }
vector<int> r, c;
int h, w, n, dx[] = { -1, 0, 1, 0, -1, 0 }, dy[] = { 0, -1, 0, 1, 0, 0 };
vector<vector<int>> g;
bool inbound(int r, int c) {
return r >= 0 && c >= 0 && r < h && c < w;
}
void upd(int r, int c, int t) {
for (int i = 0; i < 4; i++) {
int a = inbound(r + dx[i], c + dy[i]) ? g[r + dx[i]][c + dy[i]] : n;
int b = inbound(r + dx[i + 1], c + dy[i + 1]) ? g[r + dx[i + 1]][c + dy[i + 1]] : n;
if (a > g[r][c] && b > g[r][c]) {
uwu.upd(g[r][c], n - 1, t);
uwu.upd(min(a, b), n - 1, -t);
}
if (a < g[r][c] && b < g[r][c]) {
uwu.upd(max(a, b), n - 1, t);
uwu.upd(g[r][c], n - 1, -t);
}
}
}
void set(int r, int c, int v) {
for (int i = 1; i < 6; i++) {
if (!inbound(r + dx[i], c + dy[i])) continue;
upd(r + dx[i], c + dy[i], -1);
}
g[r][c] = v;
for (int i = 1; i < 6; i++) {
if (!inbound(r + dx[i], c + dy[i])) continue;
upd(r + dx[i], c + dy[i], 1);
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H * W; h = H; w = W; r = R; c = C;
uwu = segtree(0, n - 1);
g = vector<vector<int>>(H, vector<int>(W, 0));
for (int i = 0; i < n; i++) {
g[r[i]][c[i]] = i;
}
for (int i = 0; i < n; i++) {
upd(r[i], c[i], 1);
}
}
int swap_seats(int a, int b) {
set(r[a], c[a], b);
set(r[b], c[b], a);
swap(r[a], r[b]);
swap(c[a], c[b]);
return uwu.mncnt;
}
