#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int lim=1e6+100;
int n,h,w;
vector<int>r,c;
struct{
int tree[4*lim];
int P,VAL;
void update(int l,int r,int node){
if(l==r){
tree[node]=VAL;
return;
}
int mid=l+r>>1,child=node<<1;
if(P<=mid)update(l,mid,child);
else update(mid+1,r,child|1);
tree[node]=min(tree[child],tree[child|1]);
}
void update(int p,int val){
P=p,VAL=val;
update(0,lim-1,1);
}
int L,R;
int query(int l,int r,int node){
if(L<=l&&r<=R)return tree[node];
if(r<L||R<l)return INT_MAX;
int mid=l+r>>1,child=node<<1;
return min(query(l,mid,child),query(mid+1,r,child|1));
}
int query(int l,int r){
L=l,R=r;
return query(0,lim-1,1);
}
}rmin,cmin;
struct{
int tree[4*lim];
int P,VAL;
void update(int l,int r,int node){
if(l==r){
tree[node]=VAL;
return;
}
int mid=l+r>>1,child=node<<1;
if(P<=mid)update(l,mid,child);
else update(mid+1,r,child|1);
tree[node]=max(tree[child],tree[child|1]);
}
void update(int p,int val){
P=p,VAL=val;
update(0,lim-1,1);
}
int L,R;
int query(int l,int r,int node){
if(L<=l&&r<=R)return tree[node];
if(r<L||R<l)return INT_MIN;
int mid=l+r>>1,child=node<<1;
return max(query(l,mid,child),query(mid+1,r,child|1));
}
int query(int l,int r){
L=l,R=r;
return query(0,lim-1,1);
}
}rmax,cmax;
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;
r=R,c=C;
for(int i=0;i<n;i++){
updateguy(i);
}
}
int swap_seats(int x,int 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;
int rep=0;
int prev=-1;
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;
}
rep++;
assert(rep<=3000);
assert(i!=prev);
prev=i;
}
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];
// }
