#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll r[N],c[N],h,w,ans[N],a1[N],a2[N],b1[N],b2[N],vis[N];
ll lowbit(ll x){ return x&(-x); }
void add(ll x,ll v){
x++;
for(;x<=h*w;x+=lowbit(x)) ans[x]+=v;
}
ll sum(){
ll temp=0,x=h*w;
for(;x;x-=lowbit(x)) temp+=ans[x];
return temp;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
for(ll i=0;i<H*W;i++) r[i]=R[i],c[i]=C[i];
h=H,w=W;
add(0,1),vis[0]=1;
a1[0]=a2[0]=c[0],b1[0]=b2[0]=r[0];
for(ll i=1;i<h*w;i++){
a1[i]=min(a1[i-1],c[i]),a2[i]=max(a2[i-1],c[i]);
b1[i]=min(b1[i-1],r[i]),b2[i]=max(b2[i-1],r[i]);
if( (a2[i]-a1[i]+1)*(b2[i]-b1[i]+1)==i+1 ) add(i,1),vis[i]=1;
}
}
int swap_seats(int a, int b) {
swap(r[a],r[b]),swap(c[a],c[b]);
if(a>b) swap(a,b);
for(ll i=a;i<=b;i++){
if(i){
a1[i]=min(a1[i-1],c[i]),a2[i]=max(a2[i-1],c[i]);
b1[i]=min(b1[i-1],r[i]),b2[i]=max(b2[i-1],r[i]);
}
else a1[0]=a2[0]=c[0],b1[0]=b2[0]=r[0];
if( (a2[i]-a1[i]+1)*(b2[i]-b1[i]+1)==i+1 && vis[i]==0 ) add(i,1),vis[i]=1;
else if( (a2[i]-a1[i]+1)*(b2[i]-b1[i]+1)!=i+1 && vis[i]==1 ) add(i,-1),vis[i]=0;
}
return sum();
}
