#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=300007;
ll n,m,k;
vector<int>r,c;
ll sum=0;
vector<int>corr;
vector<int>ci1,ci2,cj1,cj2;
vector<int>trl,trh,tcl,tch;
void valnode(int v, int tl){
trl[v]=r[tl];
trh[v]=r[tl];
tcl[v]=c[tl];
tch[v]=c[tl];
}
void updnode(int v){
trl[v]=min(trl[2*v],trl[2*v+1]);
trh[v]=max(trh[2*v],trh[2*v+1]);
tcl[v]=min(tcl[2*v],tcl[2*v+1]);
tch[v]=max(tch[2*v],tch[2*v+1]);
}
void build(int v, int tl, int tr){
if(tl==tr){
valnode(v,tl);
}
else{
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
updnode(v);
}
}
void update(int v, int tl, int tr, int ind){
if(tl==tr){
valnode(v,tl);
}
else{
int tm=(tl+tr)/2;
if(tm>=ind){
update(2*v,tl,tm,ind);
}
else update(2*v+1,tm+1,tr,ind);
updnode(v);
}
}
pair<pii,pii>join(pair<pii,pii>x,pair<pii,pii>y){
return {{min(x.ff.ff,y.ff.ff),max(x.ff.ss,y.ff.ss)},
{min(x.ss.ff,y.ss.ff),max(x.ss.ss,y.ss.ss)}};
}
pair<pii,pii>get_val(int v, int tl, int tr, int l, int r){
if(l>r)return {{MOD,0},{MOD,0}};
if(tl==l&&tr==r)return {{trl[v],trh[v]},{tcl[v],tch[v]}};
else{
int tm=(tl+tr)/2;
return join(get_val(2*v,tl,tm,l,min(r,tm)),
get_val(2*v+1,tm+1,tr,max(l,tm+1),r));
}
}
void update_corr(int a, int b){
int i1,i2,j1,j2;
if(a!=0){
i1=ci1[a-1];
i2=ci2[a-1];
j1=cj1[a-1];
j2=cj2[a-1];
}
else{
i1=i2=r[a];
j1=j2=c[a];
}
for(int i=a;i<b;i++){
if(i1>r[i])i1=r[i];
if(i2<r[i])i2=r[i];
if(j1>c[i])j1=c[i];
if(j2<c[i])j2=c[i];
// cout<<i<<": "<<i1<<" "<<i2<<" "<<j1<<" "<<j2<<endl;
bool rgh=false;
if((j2-j1+1)*(i2-i1+1)==i+1){
rgh=true;
}
if(rgh&&!corr[i])sum++;
else if(!rgh&&corr[i])sum--;
corr[i]=rgh;
ci1[i]=i1;
ci2[i]=i2;
cj1[i]=j1;
cj2[i]=j2;
}
}
int calc_ST(){
int v=0;
int cur=0;
while(v<n*m){
// cout<<v<<endl;
pair<pii,pii>res=get_val(1,0,n*m-1,0,v);
int i1,i2,j1,j2;
i1=res.ff.ff;
i2=res.ff.ss;
j1=res.ss.ff;
j2=res.ss.ss;
if((j2-j1+1)*(i2-i1+1)==v+1){
cur++;
v++;
}
else{
v=(j2-j1+1)*(i2-i1+1)-1;
}
}
return cur;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
r=R;
c=C;
n=H;
m=W;
if(n<=1000&&m<=1000){
trl.resize(4*n*m,0);
trh.resize(4*n*m,0);
tcl.resize(4*n*m,0);
tch.resize(4*n*m,0);
build(1,0,n*m-1);
// cout<<"BUILD COMPLETED"<<endl;
return;
}
corr.resize(n*m,0);
ci1.resize(n*m,0);
ci2.resize(n*m,0);
cj1.resize(n*m,0);
cj2.resize(n*m,0);
update_corr(0,n*m);
}
int swap_seats(int a, int b) {
swap(r[a],r[b]);
swap(c[a],c[b]);
if(n<=1000&&m<=1000){
update(1,0,n*m-1,a);
update(1,0,n*m-1,b);
// cout<<"UPDATES COMPLETED"<<endl;
return calc_ST();
}
update_corr(min(a,b),max(a,b));
return sum;
}
