#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int H,W;
vector<pair<int,int>>XY;
int treeXmin[1<<19],treeXmax[1<<19],treeYmin[1<<19],treeYmax[1<<19];
int calcXmin(int l,int r){
int a=H;
l+=(1<<18);
r+=(1<<18);
while(l<=r){
a=min({a,treeXmin[l],treeXmin[r]});
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
int calcXmax(int l,int r){
int a=0;
l+=(1<<18);
r+=(1<<18);
while(l<=r){
a=max({a,treeXmax[l],treeXmax[r]});
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
int calcYmin(int l,int r){
int a=W;
l+=(1<<18);
r+=(1<<18);
while(l<=r){
a=min({a,treeYmin[l],treeYmin[r]});
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
int calcYmax(int l,int r){
int a=0;
l+=(1<<18);
r+=(1<<18);
while(l<=r){
a=max({a,treeYmax[l],treeYmax[r]});
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
int next_Xmin(int t){
int m=calcXmin(0,t);
int k=t+(1<<18);
while(m<=treeXmin[k]&&k!=1){
k=(k+1)/2;
}
while(k<(1<<18)){
if(treeXmin[k+k]<m){
k=k+k;
}
else{
k=k+k+1;
}
}
return k-(1<<18);
}
int next_Xmax(int t){
int m=calcXmax(0,t);
int k=t+(1<<18);
while(m>=treeXmax[k]&&k!=1){
k=(k+1)/2;
}
while(k<(1<<18)){
if(treeXmax[k+k]>m){
k=k+k;
}
else{
k=k+k+1;
}
}
return k-(1<<18);
}
int next_Ymin(int t){
int m=calcYmin(0,t);
int k=t+(1<<18);
while(m<=treeYmin[k]&&k!=1){
k=(k+1)/2;
}
while(k<(1<<18)){
if(treeYmin[k+k]<m){
k=k+k;
}
else{
k=k+k+1;
}
}
return k-(1<<18);
}
int next_Ymax(int t){
int m=calcYmax(0,t);
int k=t+(1<<18);
while(m>=treeYmax[k]&&k!=1){
k=(k+1)/2;
}
while(k<(1<<18)){
if(treeYmax[k+k]>m){
k=k+k;
}
else{
k=k+k+1;
}
}
return k-(1<<18);
}
void update(int x){
int t=x;
x+=(1<<18);
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.push_back({R[i],C[i]});
}
for(int i=0;i<H*W;i++){
treeXmin[i+(1<<18)]=treeXmax[i+(1<<18)]=XY[i].first;
treeYmin[i+(1<<18)]=treeYmax[i+(1<<18)]=XY[i].second;
}
treeXmin[H*W+(1<<18)]=treeYmin[H*W+(1<<18)]=-0xE869120;
treeXmax[H*W+(1<<18)]=treeYmax[H*W+(1<<18)]=0xE869120;
for(int i=(1<<18)-1;i;i--){
treeXmin[i]=min(treeXmin[i+i],treeXmin[i+i+1]);
treeXmax[i]=max(treeXmax[i+i],treeXmax[i+i+1]);
treeYmin[i]=min(treeYmin[i+i],treeYmin[i+i+1]);
treeYmax[i]=max(treeYmax[i+i],treeYmax[i+i+1]);
}
}
int swap_seats(int a,int b){
if(a>b)swap(a,b);
swap(XY[a],XY[b]);
update(a);
update(b);
int res=0;
int t=0;
while(t<H*W){
if((calcXmax(0,t)-calcXmin(0,t)+1)*(calcYmax(0,t)-calcYmin(0,t)+1)==t+1){
res++;
}
t=max(t+1,min({next_Xmin(t),next_Xmax(t),next_Ymin(t),next_Ymax(t)})-1);
}
return res;
}
