#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1e6+99,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,m,ans,A[N],B[N],mxx[N],mnx[N],mxy[N],mny[N],res[N];
set<int> R[N],C[N];
vector<int> p[N];
int get(){
f(i,0,n*m){
if(i==0){
mnx[i]=N;
mxx[i]=0;
mny[i]=N;
mxy[i]=0;
}
else{
mnx[i]=mnx[i-1];
mxx[i]=mxx[i-1];
mny[i]=mny[i-1];
mxy[i]=mxy[i-1];
}
minm(mnx[i],A[i]);
maxm(mxx[i],A[i]);
minm(mny[i],B[i]);
maxm(mxy[i],B[i]);
ans-=res[i];
res[i]=0;
if((mxx[i]-mnx[i]+1)*(mxy[i]-mny[i]+1)==i+1){
ans++;
res[i]=1;
}
}
return ans;
}
void give_initial_chart(int _n, int _m,vector<int> _A,vector<int> _B) {
n=_n,m=_m;
f(i,0,n) f(j,0,m) p[i].pb(0);
f(i,0,n*m){
A[i]=_A[i],B[i]=_B[i];
p[A[i]][B[i]]=i;
R[A[i]].insert(i);
C[B[i]].insert(i);
}
}
int swap_seats(int a, int b){
//del(A[a],B[a]);
//del(A[b],B[b]);
swap(p[A[a]][B[a]],p[A[b]][B[b]]);
swap(A[a],A[b]);
swap(B[a],B[b]);
//add(A[a],B[a]);
//add(A[b],B[b]);
return get();
}
/*
1 6 2
0 5
0 1
0 2
0 3
0 4
0 0
0 5
0 5
1 6 0
0 0
0 3
0 5
0 4
0 1
0 2
1 6 2
0 2
0 3
0 5
0 4
0 1
0 0
0 5
0 5
*/
