#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
using ii=pair<int,int>;
vector<vector<int>> g;
vector<int> R, C;
int H, W;
int dx[] = {0,-1,0,1,0};
int dy[] = {-1,0,1,0,0};
struct node {
int s, e, mn, cnt, lazy;
node *l, *r;
node(int s, int e): s(s), e(e), mn(0), cnt(e-s+1), lazy(0) {
if (s != e) {
int m = (s+e)/2;
l = new node(s,m);
r = new node(m+1,e);
}
}
void prop() {
if (lazy == 0) return;
if (s != e) {
l->lazy += lazy;
r->lazy += lazy;
}
mn += lazy;
lazy = 0;
}
void update(int x, int y, int v) {
if (x > y) return;
prop();
int m = (s+e)/2;
if (s == x && e == y) { lazy += v; return; }
else if (y <= m) l->update(x,y,v);
else if (x > m) r->update(x,y,v);
else l->update(x,m,v), r->update(m+1,y,v);
l->prop(), r->prop();
mn = min(l->mn, r->mn);
cnt = 0;
if (l->mn == mn) cnt += l->cnt;
if (r->mn == mn) cnt += r->cnt;
}
} *root;
void add(int i, int j, int val) {
int v[4] = {0}, mn = H*W;
FOR(k,0,3){
int x = i+dx[k], y = j+dy[k];
if (x >= 0 and x < H && y >= 0 and y < W) v[k] = g[x][y];
else v[k] = H*W;
if (k < 2) mn = min(mn,v[k]);
}
sort(v,v+4);
int c = g[i][j];
//TRACE(c _ mn-1 _ "|" _ v[1] _ c-1 _ "|" _ val);
root->update(c,mn-1,val);
root->update(v[1],c-1,val);
}
void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C) {
H = _H, W = _W;
R = _R, C = _C;
FOR(i,0,H-1){ g.push_back(vector<int>(W)); }
FOR(i,0,SZ(R)-1){ g[R[i]][C[i]] = i; }
root = new node(0,H*W-1);
FOR(i,0,H-1){
FOR(j,0,W-1){
add(i,j,1);
}
}
//TRACE(root->mn _ root->cnt);
}
int swap_seats(int a, int b) {
vector<ii> pts;
//TRACE(R[a] _ C[a] _ R[b] _ C[b]);
FOR(i,0,4){
int x = R[a]+dx[i], y = C[a]+dy[i];
if (x >= 0 and x < H && y >= 0 and y < W) pts.emplace_back(x,y);
}
FOR(i,0,4){
int x = R[b]+dx[i], y = C[b]+dy[i];
if (x >= 0 and x < H && y >= 0 and y < W) pts.emplace_back(x,y);
}
sort(ALL(pts));
pts.resize(unique(ALL(pts))-pts.begin());
for (ii x : pts) {
add(x.first,x.second,-1);
}
swap(g[R[a]][C[a]],g[R[b]][C[b]]);
swap(R[a],R[b]);
swap(C[a],C[b]);
for (ii x : pts) {
add(x.first,x.second,1);
}
root->prop();
return (root->mn == 1 ? root->cnt : 0);
}
