#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int lim=1e6+100;
int n,h,w;
vector<int>v[lim];
vector<int>r,c;
struct MAX{
inline static int cmp(const int& i,const int&j){
if(i<j)return j;
return i;
}
};
struct MIN{
inline static int cmp(const int& i,const int&j){
if(i>j)return j;
return i;
}
};
template<typename T,int nullval>
struct ST{
int tree[2*lim];
ST(){
for(int i=0;i<2*lim;i++)tree[i]=nullval;
}
int query(int l,int r){
int ans=nullval;
for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
if(l&1)ans=T::cmp(ans,tree[l++]);
if(r&1)ans=T::cmp(ans,tree[--r]);
}
return ans;
}
void update(int p,int val){
p+=n;
tree[p]=val;
for(p>>=1;p;p>>=1)tree[p]=T::cmp(tree[p<<1],tree[p<<1|1]);
}
};
ST<MIN,INT_MAX>cmin,rmin;
ST<MAX,INT_MIN>cmax,rmax;
void updateguy(int i){
cmax.update(i,c[i]);
cmin.update(i,c[i]);
rmax.update(i,r[i]);
rmin.update(i,r[i]);
}
void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
n=H*W;
h=H;
w=W;
for(int i=0;i<H;i++){
v[i].resize(W);
}
r=R,c=C;
for(int i=0;i<n;i++){
updateguy(i);
}
}
int swap_seats(int x,int y){
swap(v[r[x]][c[x]],v[r[y]][c[y]]);
swap(r[x],r[y]);
swap(c[x],c[y]);
updateguy(x);
updateguy(y);
// for(int i=0;i<n;i++){
// cerr<<c[i]<<' '<<r[i]<<' '<<cmax.query(i,i)<<' '<<cmin.query(i,i)<<' '<<rmax.query(i,i)<<' '<<rmin.query(i,i)<<'\n';
// }
int ans=0,mxc=INT_MIN,mxr=INT_MIN,mnr=INT_MAX,mnc=INT_MAX;
int i=0;
while(i<n){
mxc=cmax.query(0,i);
mxr=rmax.query(0,i);
mnc=cmin.query(0,i);
mnr=rmin.query(0,i);
int area=(mxc-mnc+1)*(mxr-mnr+1);
// cerr<<i<<" :: "<<mxc<<' '<<mxr<<' '<<mnr<<' '<<mnc<<" :: "<<area<<'\n';;
// assert(i+1<=area);
if(i+1==area){
ans++;
i++;
}else{
i=area-1;
}
}
return ans;
}
// std::vector<int> r;
// void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
// r = R;
// }
// int swap_seats(int a, int b) {
// return r[a];
// }
