#include "seats.h"
#include <bits/stdc++.h>
#define MAX 1000000000
using namespace std;
typedef pair<int,int> ii;
int ns;
ii val[1000010];
ii tma[4000010];
ii tmi[4000010];
void init(int node,int a,int b){
if(a==b){
tmi[node]=val[a];
tma[node]=val[a];
return;
}
int mid=(a+b)/2;
init(2*node+1,a,mid);
init(2*node+2,mid+1,b);
tma[node].first=max(tma[2*node+1].first,tma[2*node+2].first);
tma[node].second=max(tma[2*node+1].second,tma[2*node+2].second);
tmi[node].first=min(tmi[2*node+1].first,tmi[2*node+2].first);
tmi[node].second=min(tmi[2*node+1].second,tmi[2*node+2].second);
}
void update(int node,int a,int b,int id,ii va){
if(a>id or id>b) return;
if(a==b and a==id){
tma[node]=va;
tmi[node]=va;
return;
}
int le=2*node+1,ri=2*node+2,mid=(a+b)/2;
update(le,a,mid,id,va);
update(ri,mid+1,b,id,va);
tma[node].first=max(tma[le].first,tma[ri].first);
tma[node].second=max(tma[le].second,tma[ri].second);
tmi[node].first=min(tmi[le].first,tmi[ri].first);
tmi[node].second=min(tmi[le].second,tmi[ri].second);
}
ii queryma(int node,int a,int b,int l,int r){
if(a>r or l>b) return ii(-1,-1);
if(l<=a and r>=b) return tma[node];
ii res,le,ri;
int mid=(a+b)/2;
le=queryma(2*node+1,a,mid,l,r);
ri=queryma(2*node+2,mid+1,b,l,r);
res.first=max(le.first,ri.first);
res.second=max(le.second,ri.second);
return res;
}
ii querymi(int node,int a,int b,int l,int r){
if(a>r or l>b) return ii(MAX,MAX);
if(l<=a and r>=b) return tmi[node];
ii res,le,ri;
int mid=(a+b)/2;
le=querymi(2*node+1,a,mid,l,r);
ri=querymi(2*node+2,mid+1,b,l,r);
res.first=min(le.first,ri.first);
res.second=min(le.second,ri.second);
return res;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
ns=(H*W);
for(int i=0;i<R.size();i++){
val[i]=ii(R[i],C[i]);
}
init(0,0,ns-1);
}
int swap_seats(int a, int b) {
int res=0;
ii u,v;
u=val[a];
v=val[b];
swap(val[a],val[b]);
update(0,0,ns-1,a,v);
update(0,0,ns-1,b,u);
bool sw=0;
int ri,ra,ca,ci;
ri=ci=MAX;
ca=ra=-1;
for(int i=0;i<ns;i++){
if(sw==0){
ri=min(ri,val[i].first);
ra=max(ra,val[i].first);
ca=max(ca,val[i].second);
ci=min(ci,val[i].second);
}
else{
u=queryma(0,0,ns-1,0,i);
v=querymi(0,0,ns-1,0,i);
ri=v.first; ci=v.second;
ra=u.first; ca=u.second;
}
if(((ra-ri)+1)*((ca-ci)+1)==i+1) res++;
if(((ra-ri)+1)*((ca-ci)+1)>i+1){sw=1; i=((ra-ri)+1)*((ca-ci)+1)-2;}
}
return res;
}
