#include"seats.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef EVAL
#else
#include"grader.cpp"
#endif
vector<pair<int,int>>v;
#define pii pair<int,int>
int h,w;
struct node{
pii tree[4000005];
void update(int v,int l,int r,int pos,int val){
if(l==r){
tree[v]={val,val};
return;
}
int mid=(l+r)>>1;
if(pos<=mid)update(v<<1,l,mid,pos,val);
else update(v<<1|1,mid+1,r,pos,val);
tree[v]={min(tree[v<<1].first,tree[v<<1|1].first),max(tree[v<<1].second,tree[v<<1|1].second)};
}
pii get(int v,int l,int r,int ql,int qr){
if(qr<l||r<ql)return {2e9,0};
if(ql<=l&&r<=qr)return tree[v];
int mid=(l+r)>>1;
auto to1=get(v<<1,l,mid,ql,qr);
auto to2=get(v<<1|1,mid+1,r,ql,qr);
return {min(to1.first,to2.first),max(to1.second,to2.second)};
}
}tree1,tree2;
bool is[1000005];
int ans=0;
int MX=999999;
void give_initial_chart(int H,int W,vector<int>x,vector<int>y){
h=H,w=W;
int l=2e9,r=0,u=2e9,d=0;
for(int i=0;i<h*w;i++){
v.push_back({x[i],y[i]});
tree1.update(1,0,MX,i,x[i]);
tree2.update(1,0,MX,i,y[i]);
l=min(l,v[i].first);
r=max(r,v[i].first);
u=min(u,v[i].second);
d=max(d,v[i].second);
if((r-l+1)*(d-u+1)==i+1){
ans++;
is[i]=1;
}
}
}
int swap_seats(int a,int b){
tree1.update(1,0,MX,a,v[b].first);
tree2.update(1,0,MX,a,v[b].second);
tree1.update(1,0,MX,b,v[a].first);
tree2.update(1,0,MX,b,v[a].second);
swap(v[a],v[b]);
if(a>b)swap(a,b);
auto tmp=tree1.get(1,0,MX,0,a);
int l=tmp.first;
int r=tmp.second;
tmp=tree2.get(1,0,MX,0,a);
int u=tmp.first;
int d=tmp.second;
for(int i=a;i<=b;i++){
l=min(l,v[i].first);
r=max(r,v[i].first);
u=min(u,v[i].second);
d=max(d,v[i].second);
bool nw=0;
if((r-l+1)*(d-u+1)==i+1)nw=1;
ans-=is[i];
ans+=nw;
is[i]=nw;
}
return ans;
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
