#pragma GCC optimze("O2")
#include <vector>
#include <iostream>
using namespace std;
int h,w;
int const N=1e6+10;
struct node
{
int mx=0,my=0,mix=1e9,miy=1e9;
};
pair<int,int>seat[N]={};
node St[2097152]={};
bool fen[N]={};
node extra;
node comb(node a,node b)
{
node c;
c.mx=max(a.mx,b.mx);
c.mix=min(a.mix,b.mix);
c.my=max(a.my,b.my);
c.miy=min(a.miy,b.miy);
return c;
}
int ans=0;
void build(int i,int st,int en)
{
if (st==en)
{
St[i].mx=St[i].mix=seat[st].first;
St[i].my=St[i].miy=seat[st].second;
return;
}
int mid=(st+en)/2;
build(i*2,st,mid);
build(i*2+1,mid+1,en);
St[i]=comb(St[i*2],St[i*2+1]);
}
void update(int i,int r,int st,int en)
{
if (st==en)
{
St[i].mx=St[i].mix=seat[st].first;
St[i].my=St[i].miy=seat[st].second;
return;
}
int mid=(st+en)/2;
if (r<=mid)
update(i*2,r,st,mid);
else
update(i*2+1,r,mid+1,en);
St[i]=comb(St[i*2],St[i*2+1]);
}
node get(int i,int st,int en,int l,int r)
{
if (l>r)
return extra;
if (st>=l&&en<=r)
return St[i];
if (st>r||en<l)
return extra;
int mid=(st+en)/2;
return comb(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
}
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++)
seat[i]={R[i],C[i]};
build(1,0,h*w-1);
int x=0,mx=1e9;
int y=0,my=1e9;
for (int k=0;k<h*w;k++)
{
x=max(x,seat[k].first);
mx=min(mx,seat[k].first);
y=max(y,seat[k].second);
my=min(my,seat[k].second);
if ((x-mx+1)*(y-my+1)==k+1)
{
fen[k]=1;
ans++;
}
}
}
int swap_seats(int a, int b)
{
swap(seat[a],seat[b]);
update(1,min(a,b),0,h*w-1);
update(1,max(a,b),0,h*w-1);
int x=0,mx=1e9;
int y=0,my=1e9;
node z=get(1,0,h*w-1,0,min(a,b)-1);
x=z.mx,y=z.my;
mx=z.mix,my=z.miy;
for (int k=min(a,b);k<=max(a,b);k++)
{
x=max(x,seat[k].first);
mx=min(mx,seat[k].first);
y=max(y,seat[k].second);
my=min(my,seat[k].second);
if ((x-mx+1)*(y-my+1)==k+1)
{
if (fen[k]==0)
ans++;
fen[k]=1;
}
else
{
if (fen[k])
ans--;
fen[k]=0;
}
}
return ans;
}
