#include"seats.h"
#include<bits/stdc++.h>
using namespace std;
#ifndef EVAL
#include"grader.cpp"
#endif
vector<pair<int,int>>v;
#define pii pair<int,int>
int h,w;
struct node{
int l,r,u,d;
node(int x,int y){
l=r=x;
u=d=y;
}
node(){
l=u=2e9;
r=d=0;
}
}tree[4000000];
int num=1048576-1;
node combine(node l,node r){
node res;
res.l=min(l.l,r.l);
res.r=max(l.r,r.r);
res.u=min(l.u,r.u);
res.d=max(l.d,r.d);
return res;
}
void update(int pos,int x,int y){
pos+=num;
tree[pos]=node(x,y);
pos>>=1;
while(pos){
tree[pos]=combine(tree[pos<<1],tree[pos<<1|1]);
pos>>=1;
}
}
node get(int l,int r){
l+=num;
r+=num;
node res=node();
while(l<=r){
if(l&1)
res=combine(res,tree[l++]);
if(!(r&1))
res=combine(res,tree[r--]);
l>>=1;
r>>=1;
}
return res;
}
void give_initial_chart(int H,int W,vector<int>x,vector<int>y){
for(int i=0;i<4000000;i++)tree[i]=node();
h=H,w=W;
for(int i=0;i<h*w;i++){
v.push_back({x[i],y[i]});
update(i,x[i],y[i]);
}
}
int swap_seats(int a,int b){
update(a,v[b].first,v[b].second);
update(b,v[a].first,v[a].second);
swap(v[a],v[b]);
int ans=0;
for(int i=0;i<h*w;i++){
node tmp=get(0,i);
if((tmp.r-tmp.l+1)*(tmp.d-tmp.u+1)==i+1)ans++;
else i=(tmp.r-tmp.l+1)*(tmp.d-tmp.u+1)-2;
}
return ans;
}
