#include"seats.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef EVAL
#else
#include"grader.cpp"
#endif
vector<pair<int,int>>v;
#define pii pair<int,int>
int h,w;
struct node{
pii tree[4000005];
void update(int v,int l,int r,int pos,int val){
if(l==r){
tree[v]={val,val};
return;
}
int mid=(l+r)>>1;
if(pos<=mid)update(v<<1,l,mid,pos,val);
else update(v<<1|1,mid+1,r,pos,val);
tree[v]={min(tree[v<<1].first,tree[v<<1|1].first),max(tree[v<<1].second,tree[v<<1|1].second)};
}
pii get(int v,int l,int r,int ql,int qr){
if(qr<l||r<ql)return {2e9,0};
if(ql<=l&&r<=qr)return tree[v];
int mid=(l+r)>>1;
auto to1=get(v<<1,l,mid,ql,qr);
auto to2=get(v<<1|1,mid+1,r,ql,qr);
return {min(to1.first,to2.first),max(to1.second,to2.second)};
}
}tree1,tree2;
int MX=999999;
void give_initial_chart(int H,int W,vector<int>x,vector<int>y){
h=H,w=W;
for(int i=0;i<h*w;i++){
v.push_back({x[i],y[i]});
tree1.update(1,0,MX,i,x[i]);
tree2.update(1,0,MX,i,y[i]);
}
}
int swap_seats(int a,int b){
tree1.update(1,0,MX,a,v[b].first);
tree2.update(1,0,MX,a,v[b].second);
tree1.update(1,0,MX,b,v[a].first);
tree2.update(1,0,MX,b,v[a].second);
swap(v[a],v[b]);
int ans=0;
for(int i=0;i<h*w;i++){
auto tmp=tree1.get(1,0,MX,0,i);
int l=tmp.first;
int r=tmp.second;
tmp=tree2.get(1,0,MX,0,i);
int u=tmp.first;
int d=tmp.second;
if((r-l+1)*(d-u+1)==i+1)ans++;
else i=(r-l+1)*(d-u+1)-2;
}
return ans;
}
