/*
_____________________.
|____________________| $$\ $$\ $$\ $$\
|____________________| $$ | \__| $$ | $$ |
|____________________| $$$$$$\ $$$$$$\ $$$$$$\ $$$$$$$\ $$$$$$$\ $$$$$$\ $$\ $$$$$$\ $$$$$$$\ $$$$$$\ $$$$$$$\
|____________________| \_$$ _| $$ __$$\ \____$$\ $$ __$$\ $$ _____| $$ __$$\ $$ |$$ __$$\ $$ __$$\\_$$ _| $$ _____|
|____________________| $$ | $$ | \__|$$$$$$$ |$$ | $$ |\$$$$$$\ $$ | \__|$$ |$$ / $$ |$$ | $$ | $$ | \$$$$$$\
$$ |$$\ $$ | $$ __$$ |$$ | $$ | \____$$\ $$ | $$ |$$ | $$ |$$ | $$ | $$ |$$\ \____$$\
\$$$$ |$$ | \$$$$$$$ |$$ | $$ |$$$$$$$ | $$ | $$ |\$$$$$$$ |$$ | $$ | \$$$$ |$$$$$$$ |
へ ♡ \____/ \__| \_______|\__| \__|\_______/ \__| \__| \____$$ |\__| \__| \____/ \_______/
૮ - ՛) $$\ $$ |
/ ⁻ ៸| \$$$$$$ | are human rights :3
乀 (ˍ,ل ل \______/
*/
//#include "candies_ioi.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<pair<T, long long>, null_type,
less<pair<T, long long>>, rb_tree_tag,
tree_order_statistics_node_update>;
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf (ll)2e12+4
#define pb push_back
#define se second
#define fi first
#define endl '\n'
#define mp make_pair
#define pll pair<ll,ll>
#define kth_smallest find_by_order
#define num_of_smaller order_of_key
#define fori(x) for(ll i=0;i<x;i++)
#define forj(y) for(ll j=0;j<y;j++)
#define fork(z) for(ll k=0;k<z;k++)
#define DEBUG
#ifdef DEBUG
#define show(x) cerr<<#x<<" is "<<x<<endl;
#define show2(x,y) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define show3(x,y,z) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<endl;
#define show4(x,y,z,a) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<" "<<#a<<" is "<<a<<endl;
#define show_vec(a) for(auto &i:a)cerr<<i<<" ";cerr<<endl;
#define skillissue cerr<<"your code is running\n";
#define getchar_unlocked _getchar_nolock // comment before submission
#else
#define show(x)
#define show2(x,y)
#define show3(x,y,z)
#define show4(x,y,z,a)
#define show_vec(a)
#define skillissue
#endif
#include "seats.h"
std::vector<int> r;
struct node{
ll S,E,M;
pair<pll,ll>val;
pll lazy;
node *l,*r;
node(ll s,ll e){
S=s;E=e;val=mp(mp(0,0),E-S+1);
lazy=mp(0,0);
M=(S+E)/2;
if(S==E)return;
l=new node(S,M);
r=new node(M+1,E);
}
pair<pll,ll> merge(pair<pll,ll>a,pair<pll,ll>b){
if(a.fi==b.fi)return mp(a.fi,a.se+b.se);
if(a.fi<b.fi){
return a;
}
return b;
}
void prop(){
if(S==E)return;
l->val.fi.fi+=lazy.fi;
l->val.fi.se+=lazy.se;
r->val.fi.fi+=lazy.fi;
r->val.fi.se+=lazy.se;
l->lazy.fi+=lazy.fi;
r->lazy.fi+=lazy.fi;
l->lazy.se+=lazy.se;
r->lazy.se+=lazy.se;
lazy=mp(0,0);
}
void oneup(ll x,ll y,ll v){
if(x>E or y<S)return;
if(x<=S and E<=y){
lazy.fi+=v;
val.fi.fi+=v;
return;
}
prop();
l->oneup(x,y,v);
r->oneup(x,y,v);
val=merge(l->val,r->val);
}
void threeup(ll x,ll y,ll v){
if(x>E or y<S)return;
if(x<=S and E<=y){
lazy.se+=v;
val.fi.se+=v;
return;
}
prop();
l->threeup(x,y,v);
r->threeup(x,y,v);
val=merge(l->val,r->val);
}
pair<pll,ll> qry(ll x,ll y){
if(x>E or y<S)return mp(mp(inf,inf),0);
if(x<=S and E<=y){
return val;
}
prop();
return merge(l->qry(x,y),r->qry(x,y));
}
};
const ll maxn=(ll)1e6+5;
node *root=new node(0,maxn);
ll n;
ll ans;
ll posx[maxn];
ll posy[maxn];
ll h,w;
vector<vector<ll>>grid;
pll contri[maxn];
void up(int i,int j){
if(i<=0 or j<=0 or i>h or j>w)return;
ll tmp=0,tmp1=0;
for(ll x=i-1;x<=i;x++)for(ll y=j-1;y<=j;y++){
// this is topleft
ll prev=0;
for(ll dx=0;dx<=1;dx++){
for(ll dy=0;dy<=1;dy++){
if(grid[x+dx][y+dy]<grid[i][j]){
prev++;
}
}
}
//show3(x,y,prev)
if(prev==2){
tmp1++;
}else if(prev==0){
tmp++;
}
else if(prev==1){
tmp--;
}
else{
tmp1--;
}
}
root->oneup(grid[i][j],n,-contri[grid[i][j]].fi);
root->threeup(grid[i][j],n,-contri[grid[i][j]].se);
contri[grid[i][j]]=mp(tmp,tmp1);
root->oneup(grid[i][j],n,contri[grid[i][j]].fi);
root->threeup(grid[i][j],n,contri[grid[i][j]].se);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H;w=W;
fori(H+2){
grid.pb({});
forj(W+2)grid[i].pb(inf);
}
n=(H*W);
fori(n)contri[i]=mp(0,0);
fori(n){
posx[i]=R[i];
}
fori(n){
posy[i]=C[i];
}
fori(H*W){
grid[R[i]+1][C[i]+1]=i;
}
fori(n){
up(posx[i]+1,posy[i]+1);
}
}
int swap_seats(int a, int b) {
swap(grid[posx[b]+1][posy[b]+1],grid[posx[a]+1][posy[a]+1]);
swap(posx[a],posx[b]);
swap(posy[a],posy[b]);
for(ll i=0;i<=2;i++)for(ll j=0;j<=2;j++){
up(posx[a]+i,posy[a]+j);
}
for(ll i=0;i<=2;i++)for(ll j=0;j<=2;j++){
up(posx[b]+i,posy[b]+j);
}
return root->qry(0,n-1).se;
}
