#include "seats.h"
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=1e5+500;
const ll inf=1e9+900;
ll mn[2][maxn*4];
ll mx[2][maxn*4];
ll n;
pii findM(ll b,ll L,ll R,ll node,ll l,ll r){
if(l<=L && R<=r){
return mp(mn[b][node],mx[b][node]);
}
if(R<=l || r<=L){
return mp(inf,0);
}
ll mid=(L+R)/2;
pii w1=findM(b,L,mid,2*node,l,r);
pii w2=findM(b,mid,R,2*node+1,l,r);
return mp(min(w1.F,w2.F),max(w1.S,w2.S));
}
ll nxtmn(ll b,ll L,ll R,ll node,ll v){// akharin jaee ke mn>v
if(L+1==R){
if(mn[b][node]>v)return R;
return L;
}
ll mid=(L+R)/2;
if(mn[b][2*node]>v)return nxtmn(b,mid,R,2*node+1,v);
else return nxtmn(b,L,mid,2*node ,v);
}
ll nxtmx(ll b,ll L,ll R,ll node,ll v){// akharin jaee ke mx<v
if(L+1==R){
if(mx[b][node]<v)return R;
return L;
}
ll mid=(L+R)/2;
if(mx[b][2*node]<v)return nxtmx(b,mid,R,2*node+1,v);
else return nxtmx(b,L,mid,2*node ,v);
}
vector<ll> a[2];
vector<ll> get(ll b,ll w){
vector<ll> ans;
for(ll i=0;i<=w;i++){
ans.pb(nxtmn(b,0,n,1,i)-1);
ans.pb(nxtmx(b,0,n,1,i)-1);
}
return ans;
}
void update(ll b,ll l,ll r,ll node,ll x,ll v){
if(l+1==r){
mx[b][node]=v;
mn[b][node]=v;
return;
}
ll mid=(l+r)/2;
if(x<mid)
update(b,l,mid,2*node ,x,v);
else
update(b,mid,r,2*node+1,x,v);
mn[b][node]=min(mn[b][2*node],mn[b][2*node+1]);
mx[b][node]=max(mx[b][2*node],mx[b][2*node+1]);
}
bool isGood(ll x){
pii w1=findM(0,0,n,1,0,x+1);
pii w2=findM(1,0,n,1,0,x+1);
ll r1=w1.S-w1.F+1;
ll r2=w2.S-w2.F+1;
return (r1*r2==x+1);
}
void bild(ll b,ll l,ll r,ll node){
for(ll i=0;i<n;i++){
update(b,l,r,node,i,a[b][i]);
}
}
ll ww,hh;
int findANS(){
vector<ll> imp;
if(ww+hh<2100){
imp.pb(0);
imp.pb(n-1);
vector<ll> v1=get(0,hh);
vector<ll> v2=get(1,ww);
for(auto x:v1)imp.pb(x);
for(auto x:v2)imp.pb(x);
}else{
ll ans=0;
pii w0=mp(inf,0);
pii w1=mp(inf,0);
for(ll i=0;i<n;i++){
w0.F=min(w0.F,a[0][i]);
w0.S=max(w0.S,a[0][i]);
w1.F=min(w1.F,a[1][i]);
w1.S=max(w1.S,a[1][i]);
ll r0=w0.S-w0.F+1;
ll r1=w1.S-w1.F+1;
ans+=(r0*r1==i+1);
}
return ans;
}
sort(imp.begin(),imp.end());
imp.resize(unique(imp.begin(),imp.end())-imp.begin());
ll ans=0;
for(auto x:imp){
ans+=isGood(x);
}
return ans;
}
void give_initial_chart(int H, int W,vector<int> R,vector<int> C) {
if(H>W){
swap(H,W);
swap(R,C);
}
ww=W;
hh=H;
n=W*H;
a[0]=R;
a[1]=C;
bild(0,0,n,1);
bild(1,0,n,1);
}
int swap_seats(int A, int B){
ll ra=a[0][A];
ll rb=a[0][B];
ll ca=a[1][A];
ll cb=a[1][B];
swap(a[0][A],a[0][B]);
swap(a[1][A],a[1][B]);
update(0,0,n,1,A,rb);
update(0,0,n,1,B,ra);
update(1,0,n,1,A,cb);
update(1,0,n,1,B,ca);
return findANS();
}
