#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e6+50,inf=1e9;
int n,m,res;
int X[N+50],Y[N+50],L[N+50],R[N+50],LL[N+50],RR[N+50];
struct Node{
int L,R,LL,RR;
}node[2*N];
Node Merge(Node a,Node b){return {min(a.L,b.L),max(a.R,b.R),min(a.LL,b.LL),max(a.RR,b.RR)};}
int nc,root,lc[2*N],rc[2*N];
void Update(int &c,int ss,int se,int qind,Node qval){
if(!c){c=++nc;}
if(ss==se){node[c]=qval;return;}
int mid=ss+se>>1;
if(qind<=mid) Update(lc[c],ss,mid,qind,qval);
else Update(rc[c],mid+1,se,qind,qval);
node[c]=Merge(node[lc[c]],node[rc[c]]);
}
Node Get(int &c,int ss,int se,int qs,int qe){
if(qs<=ss && se<=qe) return node[c];
if(qe<ss || se<qs) return {inf,0,inf,0};
int mid=ss+se>>1;
return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c) {
node[0]={inf,0,inf,0};
int n=H,m=W;
for(int i=1;i<=n*m;i++) X[i]=r[i-1]+1,Y[i]=c[i-1]+1;
for(int i=1;i<=n*m;i++) Update(root,1,n*m,i,{X[i],X[i],Y[i],Y[i]});
L[0]=LL[0]=inf;
for(int i=1;i<=n*m;i++){
L[i]=min(L[i-1],X[i]),R[i]=max(R[i-1],X[i]);
LL[i]=min(LL[i-1],Y[i]),RR[i]=max(RR[i-1],Y[i]);
if((R[i]-L[i]+1)*(RR[i]-LL[i]+1)==i) res++;
}
}
int swap_seats(int a, int b) {
a++,b++;
if(a>b) swap(a,b);
if(n*m<=10000){
swap(X[a],X[b]),swap(Y[a],Y[b]);
for(int i=a;i<=b;i++) if((R[i]-L[i]+1)*(RR[i]-LL[i]+1)==i) res--;
for(int i=a;i<=b;i++){
L[i]=min(L[i-1],X[i]),R[i]=max(R[i-1],X[i]);
LL[i]=min(LL[i-1],Y[i]),RR[i]=max(RR[i-1],Y[i]);
if((R[i]-L[i]+1)*(RR[i]-LL[i]+1)==i) res++;
}
return res;
}
else{
Update(root,1,n*m,b,{X[a],X[a],Y[a],Y[a]});
Update(root,1,n*m,a,{X[b],X[b],Y[b],Y[b]});
swap(X[a],X[b]),swap(Y[a],Y[b]);
int i=1,ans=0;
Node x;
while(i<=n*m){
x=Merge(x,{X[i],X[i],Y[i],Y[i]});
if((x.R-x.L+1)*(x.RR-x.LL+1)==i) ans++;
int d=min(x.R-x.L+1,x.RR-x.L);
x=Merge(x,Get(root,1,n*m,i,i+d));
i+=d;
}
return ans;
}
}
