#pragma GCC target("avx,avx2,sse,sse2")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "seats.h"
#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
using namespace std;
struct node{
int mnv, mna, lz;
};
vector<vector<int>> place;
vector<pii> pos;
vector<node> seg;
vector<pii> ord = {{0, 0},{0, -1},{-1, 0},{-1,-1}};
int N;
node conq(node& a, node& b){
node c;
if(a.mnv == b.mnv){
c.mnv = a.mnv;
c.mna = a.mna + b.mna;
}
if(a.mnv < b.mnv){
c.mnv = a.mnv;
c.mna = a.mna;
}
if(a.mnv > b.mnv){
c.mnv = b.mnv;
c.mna = b.mna;
}
return c;
}
void comb(int v){
seg[v].lz += seg[v/2].lz;
}
void appl(int v){
seg[v].mnv+=seg[v].lz;
seg[v].lz = 0;
}
void build(int v, int tl, int tr){
if(tl == tr){
seg[v].mna = 1;
return;
}
int tm = (tl+tr)/2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
}
void upd(int v, int tl, int tr, int l, int r, int val){
if(r<l)return;
if(seg[v].lz!= 0){
if(tl!=tr){
seg[2*v].lz+=seg[v].lz;
seg[2*v+1].lz+=seg[v].lz;
}
seg[v].mnv+=seg[v].lz;
seg[v].lz = 0;
}
if(tl>r || tr < l)return;
if(tl >= l && tr <= r){
seg[v].lz+= val;
if(tl!=tr){
comb(2*v);
comb(2*v+1);
}
appl(v);
return;
}
int tm = (tl+tr)/2;
upd(v*2, tl, tm, l, r, val);
upd(v*2+1, tm+1, tr, l, r, val);
seg[v] = conq(seg[2*v], seg[2*v+1]);
}
void fix(int x, int y, int val){
array<int, 4> tmp;
tmp[0] = place[x][y];
tmp[1] = place[x+1][y];
tmp[2] = place[x][y+1];
tmp[3] = place[x+1][y+1];
sort(all(tmp));
upd(1, 0, N-1, tmp[0], tmp[1]-1, val);
upd(1, 0, N-1, tmp[2], tmp[3]-1, val);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
N = H*W;
place.assign(H+2, vector<int>(W+2, H*W));
pos.assign(H*W, {0,0});
for(int i = 0; i< H*W; i++){
place[R[i]+1][C[i]+1] = i;
pos[i] = {R[i]+1, C[i]+1};
}
seg.assign(4*H*W, {0, 0, 0});
build(1, 0, N-1);
for(int i = 0; i< H+1; i++){
for(int j = 0; j < W+1; j++){
fix(i, j, 1);
}
}
}
int swap_seats(int a, int b) {
for(int i = 0; i< 2; i++){
for(int j = 0; j < 2; j++){
fix(pos[a].X-i, pos[a].Y-j, -1);
fix(pos[b].X-i, pos[b].Y-j, -1);
}
}
swap(place[pos[a].X][pos[a].Y], place[pos[b].X][pos[b].Y]);
swap(pos[a], pos[b]);
for(int i = 0; i< 2; i++){
for(int j = 0; j < 2; j++){
fix(pos[a].X-i, pos[a].Y-j, 1);
fix(pos[b].X-i, pos[b].Y-j, 1);
}
}
return seg[1].mna;
}
