#include "seats.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
const int N=3e6+5;
const int INF=1e9+5;
pair<int,int> A[N];
struct node{
int mxx, mnx, mxy,mny;
};
node tree[N];
node combine(node a, node b){
return {max(a.mxx,b.mxx),min(a.mnx,b.mnx),max(a.mxy,b.mxy),min(a.mny,b.mny)};
}
void build(int x, int l, int r, vector<pair<int,int>> &vec){
if(l==r){
tree[x]={vec[l].fr,vec[l].fr,vec[l].sc,vec[l].sc};
return;
}
int md=(l+r)/2;
build(2*x,l,md,vec);
build(2*x+1,md+1,r,vec);
tree[x]=combine(tree[2*x],tree[2*x+1]);
}
void update(int x, int l, int r, int i, pair<int,int> val){
if(l==r){
tree[x]={val.fr,val.fr,val.sc,val.sc};
return;
}
int md=(l+r)/2;
if(i<=md) update(2*x ,l ,md,i,val);
else update(2*x+1,md+1,r ,i,val);
tree[x]=combine(tree[2*x],tree[2*x+1]);
}
int find_minx(int x, int l, int r, int lx, int rx){
if(l>rx || r<lx) return INF;
if(lx<=l && r<=rx) return tree[x].mnx;
int md=(l+r)/2;
//cout<<l<<' '<<r<<' '<<lx<<' '<<rx<<endl;
return min(find_minx(2*x,l,md,lx,rx),find_minx(2*x+1,md+1,r,lx,rx));
}
int find_maxx(int x, int l, int r, int lx, int rx){
if(l>rx || r<lx) return -INF;
if(lx<=l && r<=rx) return tree[x].mxx;
int md=(l+r)/2;
return max(find_maxx(2*x,l,md,lx,rx),find_maxx(2*x+1,md+1,r,lx,rx));
}
int find_miny(int x, int l, int r, int lx, int rx){
if(l>rx || r<lx) return INF;
if(lx<=l && r<=rx) return tree[x].mny;
int md=(l+r)/2;
return min(find_miny(2*x,l,md,lx,rx),find_miny(2*x+1,md+1,r,lx,rx));
}
int find_maxy(int x, int l, int r, int lx, int rx){
if(l>rx || r<lx) return -INF;
if(lx<=l && r<=rx) return tree[x].mxy;
int md=(l+r)/2;
return max(find_maxy(2*x,l,md,lx,rx),find_maxy(2*x+1,md+1,r,lx,rx));
}
int k;
int h,w;
vector<int> R,C;
void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
R=r,C=c;
h=H,w=W;
int n=1;
while(n<H*W) n*=2;
vector<pair<int,int>> v(n);
for(int i=0;i<H*W;i++)
v[i]={R[i],C[i]};
k=n;
build(1,0,k-1,v);
}
int swap_seats(int a, int b) {
update(1,0,k-1,a,{R[b],C[b]});
update(1,0,k-1,b,{R[a],C[a]});
swap(R[a],R[b]);
swap(C[a],C[b]);
int id=1,ans=1;
while(id<h*w){
int l=find_minx(1,0,k-1,0,id);
int r=find_maxx(1,0,k-1,0,id);
int d=find_miny(1,0,k-1,0,id);
int u=find_maxy(1,0,k-1,0,id);
//cout<<R[0]<<' '<<C[0]<<endl;
//cout<<l<<' '<<r<<' '<<d<<' '<<u<<' ';
//cout<<id<<endl;
if((r-l+1)*(u-d+1)-1==id) ans++,id++;
else id=(r-l+1)*(u-d+1)-1;
}
return ans;
}
