#include "seats.h"
using namespace std;
#include <cstdio>
#include <cstdlib>
#include <vector>
std::vector<int> r;
int hmax[1000005];
int hmin[1000005];
int wmax[1000005];
int wmin[1000005];
int x[1000005];
int y[1000005];
int aint[4000005][4];
void update(int node,int st,int dr,int poz,int r,int c)
{
if(st>poz || dr<poz)
{
return;
}
if(st==dr)
{
aint[node][0]=r;
aint[node][1]=r;
aint[node][2]=c;
aint[node][3]=c;
return ;
}
int mij=(st+dr)/2;
update(node*2,st,mij,poz,r,c);
update(node*2+1,mij+1,dr,poz,r,c);
aint[node][0]=max(aint[node*2][0],aint[node*2+1][0]);
aint[node][1]=min(aint[node*2][1],aint[node*2+1][1]);
aint[node][2]=max(aint[node*2][2],aint[node*2+1][2]);
aint[node][3]=min(aint[node*2][3],aint[node*2+1][3]);
}
int v[4];
void query(int node,int st,int dr,int qst,int qdr)
{
if(st>qdr || st>dr || qst>dr || qst>qdr)
{
return;
}
if(qst<=st && dr<=qdr)
{
v[0]=max(v[0],aint[node][0]);
v[1]=min(v[1],aint[node][1]);
v[2]=max(v[2],aint[node][2]);
v[3]=min(v[3],aint[node][3]);
return ;
}
int mij=(st+dr)/2;
query(node*2,st,mij,qst,qdr);
query(node*2+1,mij+1,dr,qst,qdr);
}
int n;
int go ()
{
int poz=1,cnt=1;
v[0]=x[0];
v[1]=x[0];
v[2]=y[0];
v[3]=y[0];
while(poz<n)
{
query(1,0,n-1,0,poz);
int arie=(v[0]-v[1]+1)*(v[2]-v[3]+1);
if(arie-1==poz)
{
cnt++;
poz++;
}
else
{
poz=arie-1;
}
}
return cnt;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n=H*W;
for(int i=0;i<n;i++)
{
x[i]=R[i];
y[i]=C[i];
update(1,0,n-1,i,x[i],y[i]);
}
}
int swap_seats(int a, int b) {
swap(x[a],x[b]);
swap(y[a],y[b]);
update(1,0,n-1,a,x[a],y[a]);
update(1,0,n-1,b,x[b],y[b]);
return go ();
}
