#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ll long long
#define pll pair <ll,ll>
#define all(v) v.begin(),v.end()
#define en '\n'
#define all(v) v.begin(),v.end()
const int N = 1e6 + 10;
int n,m,k;
pii c[N];
int cnt[N * 4];
pii t[N * 4],t1[N * 4];
void merge(int v) {
t[v] = min(t[v + v],t[v + v + 1]);
cnt[v] = 0;
if(t[v + v] == t[v])cnt[v] += cnt[v + v];
if(t[v + v + 1] == t[v])cnt[v] += cnt[v + v + 1];
}
void push(int v) {
if(t1[v].f) {
t[v + v].f += t1[v].f;
t[v + v + 1].f += t1[v].f;
t1[v + v].f += t1[v].f;
t1[v + v + 1].f += t1[v].f;
t1[v].f = 0;
}
if(t1[v].s) {
t[v + v].s += t1[v].s;
t[v + v + 1].s += t1[v].s;
t1[v + v].s += t1[v].s;
t1[v + v + 1].s += t1[v].s;
t1[v].s = 0;
}
}
void upd(int v,int tl,int tr,int l,int r,int x,bool typ) {
if(tl > r || tr < l)return;
if(tl >= l && tr <= r) {
if(!typ) {
t[v].f += x;
t1[v].f += x;
}else {
t[v].s += x;
t1[v].s += x;
}
return;
}
push(v);
int tm = (tl + tr) / 2;
upd(v + v,tl,tm,l,r,x,typ);
upd(v + v + 1,tm + 1,tr,l,r,x,typ);
merge(v);
}
void out(int v,int tl,int tr) {
cout << tl << " " << tr << " with " << t[v].f << " " << t[v].s << " and " << cnt[v] << endl;
if(tl == tr)return;
push(v);
int tm = (tl + tr) / 2;
out(v + v,tl,tm);
out(v + v + 1,tm + 1,tr);
}
vector <vector <int> > num,was1;
int tim;
int dob[N],dob1[N],L,R;
void change(int x,int y,int delt,int typ = -1) {
if(was1[x][y] == tim)return;
was1[x][y] = tim;
int mn = k + 10,mn1 = k + 10,mx = -1,mx1 = -1;
for(int i = x;i <= x + 1;i++) {
for(int j = y;j <= y + 1;j++) {
if(i <= 0 || i > n || j <= 0 || j > m) {
mx1 = mx;
mx = k + 1;
if(k + 1 < mn) {
mn1 = mn;
mn = k + 1;
}else {
mn1 = min(mn1,k + 1);
}
continue;
}
if(num[i][j] < mn) {
mn1 = mn;
mn = num[i][j];
}else {
mn1 = min(mn1,num[i][j]);
}
if(num[i][j] > mx) {
mx1 = mx;
mx = num[i][j];
}else {
mx1 = max(mx1,num[i][j]);
}
}
}
if(typ == 1) {
dob[mn] += delt;
dob[mn1] -= delt;
dob1[mx1] += delt;
dob1[mx] -= delt;
return;
}
if(mn1 - 1 >= L && mn <= R)upd(1,0,k,max(mn,L),min(mn1 - 1,R),delt,1);
if(mx - 1 >= L && mx1 <= R)upd(1,0,k,max(mx1,L),min(mx - 1,R),delt,0);
}
void add(int x,int typ = -1) {
for(int i = -1;i <= 0;i++) {
for(int j = -1;j <= 0;j++) {
change(c[x].f + i,c[x].s + j,1,typ);
}
}
}
void del(int x) {
for(int i = -1;i <= 0;i++) {
for(int j = -1;j <= 0;j++) {
change(c[x].f + i,c[x].s + j,-1,-1);
}
}
}
pii d[N];
void build(int v,int tl,int tr) {
if(tl == tr) {
t[v] = d[tl];
cnt[v] = 1;
return;
}
int tm = (tl + tr) / 2;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
merge(v);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H;
m = W;
vector <int> empt;
empt.assign(m + 1,0);
num.assign(n + 1,empt);
was1 = num;
k = n * m - 1;
for(int i = 0;i <= k;i++) {
c[i] = mp(R[i] + 1,C[i] + 1);
num[c[i].f][c[i].s] = i;
}
// cout << "well" << endl;
++tim;
for(int i = 0;i <= k;i++) {
// cout << i << endl;
add(i,1);
}
int tek = 0,tek1 = 0;
for(int i = 0;i <= k;i++) {
tek += dob[i];
tek1 += dob1[i];
d[i] = mp(tek1,tek);
}
build(1,0,k);
// out(1,0,k);
}
int swap_seats(int a, int b) {
if(a > b)swap(a,b);
L = a;
R = b;
++tim;
del(a);
del(b);
swap(c[a],c[b]);
num[c[a].f][c[a].s] = a;
num[c[b].f][c[b].s] = b;
++tim;
add(a);
add(b);
// out(1,0,k);
return cnt[1];
}
