#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
struct vertex {
int lv, rv;
array<int, 2> cnt;
int convex = 0, corner = 0;
};
constexpr int MAX = 5e6;
vertex st[MAX];
int t = 0;
template<size_t N>
array<int, N> operator+(array<int, N> &f, array<int, N> &s) {
array<int, N> res;
for (int i = 0; i < N; i++)
res[i] = f[i] + s[i];
return res;
}
int build(int tl, int tr) {
if (tl + 1 == tr) {
st[++t].cnt = {1, 0};
return t;
}
int tm = (tl + tr) / 2;
int v = ++t;
st[v].lv = build(tl, tm), st[v].rv = build(tm, tr);
st[v].cnt = st[st[v].lv].cnt + st[st[v].rv].cnt;
return v;
}
void update(int v, int tl, int tr, int l, int r, int convex, int corner) {
if (l >= r)
return;
if (l == tl && r == tr)
st[v].convex += convex, st[v].corner += corner;
else {
int tm = (tl + tr) / 2;
update(st[v].lv, tl, tm, l, min(r, tm), convex, corner);
update(st[v].rv, tm, tr, max(l, tm), r, convex, corner);
}
if (tl + 1 == tr)
st[v].cnt = {1, 0};
else
st[v].cnt = st[st[v].lv].cnt + st[st[v].rv].cnt;
if (st[v].corner == 1) {
st[v].cnt[1] = st[v].cnt[0];
st[v].cnt[0] = 0;
}
if (st[v].corner > 1 || st[v].convex)
st[v].cnt = {0, 0};
}
pii convex[MAX], corner[MAX], p_inv[MAX];
vector<vector<int>> B;
int H, W;
int get(int i, int j) {
if (i < 0 || i >= H || j < 0 || j >= W)
return H * W;
return B[i][j];
}
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
void update(int i, int j, bool s = false) {
if (i < 0 || i >= H || j < 0 || j >= W)
return;
int x = B[i][j];
if (!s) {
update(1, 0, H * W, convex[x].first, convex[x].second, -1, 0);
update(1, 0, H * W, corner[x].first, corner[x].second, 0, -1);
}
corner[x] = {x, min(get(i - 1, j), get(i, j - 1))};
vector<int> val;
for (int d = 0; d < 4; d++)
val.push_back(get(i + dx[d], j + dy[d]));
sort(val.begin(), val.end());
convex[x] = {val[1], x};
update(1, 0, H * W, convex[x].first, convex[x].second, 1, 0);
update(1, 0, H * W, corner[x].first, corner[x].second, 0, 1);
}
void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
H = _H, W = _W;
B.resize(H, vector<int>(W));
for (int i = 0; i < H * W; i++) {
B[R[i]][C[i]] = i;
p_inv[i] = {R[i], C[i]};
}
build(0, H * W);
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
update(i, j, true);
}
int swap_seats(int a, int b) {
auto [i1, j1] = p_inv[a];
auto [i2, j2] = p_inv[b];
swap(B[i1][j1], B[i2][j2]);
swap(p_inv[a], p_inv[b]);
update(i1, j1), update(i2, j2);
for (int d = 0; d < 4; d++){
update(i1 + dx[d], j1 + dy[d]);
update(i2 + dx[d], j2 + dy[d]);
}
return st[1].cnt[1];
}
