#include "seats.h"
#include <algorithm>
#include <vector>
#define N_ 1010000
#define SZ 1048576
#define pii pair<int,int>
using namespace std;
vector<vector<int> >w;
int H, W, n, dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
struct point {
int x, y;
}P[N_];
int Get(int x, int y) {
if (x < 0 || x >= H || y < 0 || y >= W)return n;
return w[x][y];
}
struct Seg {
int Mn[SZ + SZ];
int C[SZ + SZ];
int K[SZ + SZ];
void UDT(int nd) {
int mm = min(Mn[nd * 2], Mn[nd * 2 + 1]);
Mn[nd] = mm;
C[nd] = 0;
if (mm == Mn[nd * 2])C[nd] += C[nd * 2];
if (mm == Mn[nd * 2 + 1])C[nd] += C[nd * 2 + 1];
}
void init(int nd, int b, int e) {
if (b == e) {
C[nd] = 1;
return;
}
int m = (b + e) >> 1;
init(nd * 2, b, m);
init(nd * 2 + 1, m + 1, e);
UDT(nd);
}
void Add2(int nd, int x) {
Mn[nd] += x;
K[nd] += x;
}
void Spread(int nd) {
Add2(nd * 2, K[nd]);
Add2(nd * 2 + 1, K[nd]);
K[nd] = 0;
}
void Add(int nd, int b, int e, int s, int l, int x) {
if (b == s && e == l) {
Add2(nd, x);
return;
}
Spread(nd);
int m = (b + e) >> 1;
if (s <= m)Add(nd * 2, b, m, s, min(m, l), x);
if (l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, x);
UDT(nd);
}
}T;
void Put(int x, int y, int ck) {
int i, j;
if (x < 0 || x >= H || y < 0 || y >= W)return;
int t = min(Get(x - 1, y), Get(x, y - 1));
if (w[x][y] < t)T.Add(1, 0, n - 1, w[x][y], t - 1, ck);
int TP[4];
for (i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
TP[i] = Get(tx, ty);
}
sort(TP, TP + 4);
if (TP[1] < w[x][y]) T.Add(1, 0, n - 1, TP[1], w[x][y] - 1, ck);
}
void give_initial_chart(int HH, int WW, std::vector<int> R, std::vector<int> C) {
int i, j;
H = HH;
W = WW;
n = H*W;
w.resize(H);
T.init(1, 0, n - 1);
for (i = 0; i < H; i++)w[i].resize(W);
for (i = 0; i < n; i++) {
P[i] = { R[i],C[i] };
w[R[i]][C[i]] = i;
}
for (i = 0; i < H; i++)for (j = 0; j < W; j++) {
Put(i, j, 1);
}
}
int swap_seats(int a, int b) {
vector<pii>TP;
TP.push_back({ P[a].x,P[a].y });
TP.push_back({ P[b].x,P[b].y });
for (int i = 0; i < 4; i++) {
TP.push_back({ P[a].x + dx[i], P[a].y + dy[i] });
TP.push_back({ P[b].x + dx[i], P[b].y + dy[i] });
}
sort(TP.begin(), TP.end());
TP.resize(unique(TP.begin(), TP.end()) - TP.begin());
for (auto &t : TP) {
Put(t.first, t.second, -1);
}
swap(w[P[a].x][P[a].y], w[P[b].x][P[b].y]);
swap(P[a], P[b]);
for (auto &t : TP) {
Put(t.first, t.second, 1);
}
return T.C[1];
}
