/// simba :(
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int N, M, K;
vector<int> X, Y;
vector< vector<int> > A;
class SegmentTree
{
public:
int N;
int sti, dri, val;
vector<int> aint, add, cnt;
void B(int nod, int st, int dr)
{
aint[nod] = add[nod] = 0, cnt[nod] = dr - st + 1;
if(st == dr) return;
B(nod * 2, st, st + (dr - st) / 2);
B(nod * 2 + 1, st + (dr - st) / 2 + 1, dr);
}
void U(int nod, int st, int dr)
{
if(sti <= st && dr <= dri)
{
aint[nod] += val;
add[nod] += val;
return;
}
int mij = st + (dr - st) / 2;
if(add[nod])
{
aint[nod * 2] += add[nod];
aint[nod * 2 + 1] += add[nod];
add[nod * 2] += add[nod];
add[nod * 2 + 1] += add[nod];
add[nod] = 0;
}
if(sti <= mij) U(nod * 2, st, mij);
if(mij < dri) U(nod * 2 + 1, mij + 1, dr);
aint[nod] = min(aint[nod * 2], aint[nod * 2 + 1]);
cnt[nod] = 0;
if(aint[nod] == aint[nod * 2]) cnt[nod] += cnt[nod * 2];
if(aint[nod] == aint[nod * 2 + 1]) cnt[nod] += cnt[nod * 2 + 1];
}
void build(int _N)
{
N = _N;
aint.resize(4 * N), add.resize(4 * N), cnt.resize(4 * N);
B(1, 0, N - 1);
}
void update(int st, int dr, int v)
{
if(st > dr) return;
sti = st, dri = dr, val = v;
U(1, 0, N - 1);
}
int query()
{
return cnt[1];
}
}aint;
int a(int x, int y)
{
if(x < 0 || y < 0 || x >= N || y >= M) return K;
return A[x][y];
}
void makeBlack(int x, int y, int add)
{
if(x < 0 || y < 0 || x >= N || y >= M) return;
int t = min(a(x - 1, y), a(x, y - 1));
aint.update(a(x, y), t - 1, add);
}
void makeWhite(int x, int y, int add)
{
if(x < 0 || y < 0 || x >= N || y >= M) return;
vector<int> t;
t.push_back(a(x - 1, y));
t.push_back(a(x + 1, y));
t.push_back(a(x, y - 1));
t.push_back(a(x, y + 1));
sort(t.begin(), t.end());
int tt = t[1];
aint.update(tt, a(x, y) - 1, add);
}
void solveCell(int x, int y, int add)
{
makeBlack(x, y, add);
makeBlack(x + 1, y, add);
makeBlack(x, y + 1, add);
makeWhite(x, y, add);
makeWhite(x - 1, y, add);
makeWhite(x + 1, y, add);
makeWhite(x, y - 1, add);
makeWhite(x, y + 1, add);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
N = H, M = W;
K = N * M;
X = R, Y = C;
A.resize(N);
for(int i = 0; i < N; i++) A[i].resize(M);
for(int i = 0; i < K; i++)
A[ X[i] ][ Y[i] ] = i;
aint.build(K);
for(int i = 0; i < K; i++)
{
makeBlack(X[i], Y[i], 1);
makeWhite(X[i], Y[i], 1);
}
}
int swap_seats(int a, int b)
{
solveCell(X[a], Y[a], -1);
solveCell(X[b], Y[b], -1);
swap(X[a], X[b]);
swap(Y[a], Y[b]);
A[ X[a] ][ Y[a] ] = a;
A[ X[b] ][ Y[b] ] = b;
solveCell(X[a], Y[a], 1);
solveCell(X[b], Y[b], 1);
return aint.query();
}
