#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int H,W;
pair<int,int>XY[1000000];
int treeXmin[1<<21],treeXmax[1<<21],treeYmin[1<<21],treeYmax[1<<21];
inline int calcXmin(int l,int r){
int a=H;
l+=(1<<20);
r+=(1<<20);
while(l<=r){
if(a<treeXmin[l]&&a<treeXmin[r]){
}
else if(treeXmin[l]<treeXmin[r]){
a=treeXmin[l];
}
else{
a=treeXmin[r];
}
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
inline int calcXmax(int l,int r){
int a=0;
l+=(1<<20);
r+=(1<<20);
while(l<=r){
if(a>treeXmax[l]&&a>treeXmax[r]){
}
else if(treeXmax[l]>treeXmax[r]){
a=treeXmax[l];
}
else{
a=treeXmax[r];
}
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
inline int calcYmin(int l,int r){
int a=W;
l+=(1<<20);
r+=(1<<20);
while(l<=r){
if(a<treeYmin[l]&&a<treeYmin[r]){
}
else if(treeYmin[l]<treeYmin[r]){
a=treeYmin[l];
}
else{
a=treeYmin[r];
}
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
inline int calcYmax(int l,int r){
int a=0;
l+=(1<<20);
r+=(1<<20);
while(l<=r){
if(a>treeYmax[l]&&a>treeYmax[r]){
}
else if(treeYmax[l]>treeYmax[r]){
a=treeYmax[l];
}
else{
a=treeYmax[r];
}
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
inline int next(int t,int a,int b,int c,int d){
int k=t+(1<<20);
while(a<=treeXmin[k]&&treeXmax[k]<=b&&c<=treeYmin[k]&&treeYmax[k]<=d&&k!=1){
k=(k+1)/2;
}
while(k<(1<<20)){
if(treeXmin[k+k]<a||b<treeXmax[k+k]||treeYmin[k+k]<c||d<treeYmax[k+k]){
k=k+k;
}
else{
k=k+k+1;
}
}
return k-(1<<20);
}
void update(int x){
int t=x;
x+=(1<<20);
treeXmin[x]=treeXmax[x]=XY[t].first;
treeYmin[x]=treeYmax[x]=XY[t].second;
while(x){
x/=2;
treeXmin[x]=min(treeXmin[x+x],treeXmin[x+x+1]);
treeXmax[x]=max(treeXmax[x+x],treeXmax[x+x+1]);
treeYmin[x]=min(treeYmin[x+x],treeYmin[x+x+1]);
treeYmax[x]=max(treeYmax[x+x],treeYmax[x+x+1]);
}
}
void give_initial_chart(int h,int w,vector<int>R,vector<int>C){
H=h;
W=w;
for(int i=0;i<H*W;i++){
XY[i]={R[i],C[i]};
}
for(int i=0;i<H*W;i++){
treeXmin[i+(1<<20)]=treeXmax[i+(1<<20)]=XY[i].first;
treeYmin[i+(1<<20)]=treeYmax[i+(1<<20)]=XY[i].second;
}
treeXmin[H*W+(1<<20)]=treeYmin[H*W+(1<<20)]=-0xE869120;
treeXmax[H*W+(1<<20)]=treeYmax[H*W+(1<<20)]=0xE869120;
for(int i=(1<<20)-1;i;i--){
if(treeXmin[i+i]<treeXmin[i+i+1]){
treeXmin[i]=treeXmin[i+i];
}
else{
treeXmin[i]=treeXmin[i+i+1];
}
if(treeXmax[i+i]>treeXmax[i+i+1]){
treeXmax[i]=treeXmax[i+i];
}
else{
treeXmax[i]=treeXmax[i+i+1];
}
if(treeYmin[i+i]<treeYmin[i+i+1]){
treeYmin[i]=treeYmin[i+i];
}
else{
treeYmin[i]=treeYmin[i+i+1];
}
if(treeYmax[i+i]>treeYmax[i+i+1]){
treeYmax[i]=treeYmax[i+i];
}
else{
treeYmax[i]=treeYmax[i+i+1];
}
}
}
int swap_seats(int a,int b){
swap(XY[a],XY[b]);
update(a);
update(b);
int res=0;
int t=0;
while(t<H*W){
int p,q,r,s;
p=calcXmax(0,t);
q=calcXmin(0,t);
r=calcYmax(0,t);
s=calcYmin(0,t);
if((p-q+1)*(r-s+1)==t+1){
res++;
}
t=max(t+1,next(t,q,p,s,r)-1);
}
return res;
}
