#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+100;
struct node{
int mnx;
int mny;
int mxx;
int mxy;
};
node INF;
int n;
node seg[4*N];
inline node com(node a,node b)
{
node ret;
ret.mnx=min(a.mnx,b.mnx);
ret.mny=min(a.mny,b.mny);
ret.mxx=max(a.mxx,b.mxx);
ret.mxy=max(a.mxy,b.mxy);
return ret;
}
void update(int p,int s,int e,int&i,int&x,int&y)
{
if(s==e){
seg[p].mnx=x;
seg[p].mxx=x;
seg[p].mny=y;
seg[p].mxy=y;
return;
}
int mid=(s+e)/2;
if(i<=mid){
update(p*2,s,mid,i,x,y);
}
else{
update(p*2+1,mid+1,e,i,x,y);
}
seg[p]=com(seg[p*2],seg[p*2+1]);
}
void fix(node u)
{
cout<<u.mnx<<" "<<u.mxx<<endl;
cout<<u.mny<<" "<<u.mxy<<endl;
}
node get(int p,int s,int e,int&a,int&b)
{
// cout<<"\n";
//cout<<s<<" "<<e<<endl;
// fix(seg[p]);
// cout<<"\n";
if(a<=s&&e<=b)return seg[p];
if(s>b||e<a)return INF;
int mid=(s+e)/2;
return com(
get(p*2 ,s ,mid,a,b),
get(p*2+1,mid+1,e ,a,b)
);
}
void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
INF.mnx=1e7;
INF.mny=1e7;
INF.mxx=-1e7;
INF.mxy=-1e7;
n=H*W;
for(int i=0;i<n;i++){
update(1,0,n-1,i,R[i],C[i]);
}
}
int z=0;
int swap_seats(int a, int b){
// cout<<"\n";
// cout<<"\n";
node aa=get(1,0,n-1,a,a);
node bb=get(1,0,n-1,b,b);
update(1,0,n-1,a,bb.mnx,bb.mny);
update(1,0,n-1,b,aa.mnx,aa.mny);
int i=0,ret=0;
while(i<n){
node u=get(1,0,n-1,z,i);
int k=(u.mxx-u.mnx+1)*(u.mxy-u.mny+1);
//fix(u);
if(k==i+1){
ret++;
i++;
}
else{
i=k-1;
}
}
return ret;
}
