#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include "seats.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
const int MAXN=1e6+2;
int H,W;
vector<int> X,Y;
int sgt[4*MAXN][4]; //X(min,max) Y(min,max)
void build(int p=1, int l=0, int r=H*W-1)
{
if(l==r)
{
sgt[p][0]=X[l];
sgt[p][1]=X[l];
sgt[p][2]=Y[l];
sgt[p][3]=Y[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
sgt[p][0]=min(sgt[p*2][0], sgt[p*2+1][0]);
sgt[p][2]=min(sgt[p*2][2], sgt[p*2+1][2]);
sgt[p][1]=max(sgt[p*2][1], sgt[p*2+1][1]);
sgt[p][3]=max(sgt[p*2][3], sgt[p*2+1][3]);
}
void update(int id, int p=1, int l=0, int r=H*W-1)
{
if(l==r)
{
sgt[p][0]=X[l];
sgt[p][1]=X[l];
sgt[p][2]=Y[l];
sgt[p][3]=Y[l];
return;
}
int mid=(l+r)/2;
if(id<=mid) update(id,p*2,l,mid);
else update(id,p*2+1,mid+1,r);
sgt[p][0]=min(sgt[p*2][0], sgt[p*2+1][0]);
sgt[p][2]=min(sgt[p*2][2], sgt[p*2+1][2]);
sgt[p][1]=max(sgt[p*2][1], sgt[p*2+1][1]);
sgt[p][3]=max(sgt[p*2][3], sgt[p*2+1][3]);
}
pair<pair<int,int>,pair<int,int>> get(int a, int b, int p=1, int l=0, int r=H*W-1)
{
if(l==r) return {{sgt[p][0],sgt[p][1]},{sgt[p][2],sgt[p][3]}};
int mid=(l+r)>>1; // l mid a b
int mnX=1e9, mxX=-1, mnY=1e9, mxY=-1;
if(l<=b && mid>=a)
{
auto pr=get(a,b,p*2,l,mid);
mnX=min(mnX,pr.x.x);
mxX=max(mxX,pr.x.y);
mnY=min(mnY,pr.y.x);
mxY=max(mxY,pr.y.y);
}
if(mid+1<=b && r>=a)
{
auto pr=get(a,b,p*2+1,mid+1,r);
mnX=min(mnX,pr.x.x);
mxX=max(mxX,pr.x.y);
mnY=min(mnY,pr.y.x);
mxY=max(mxY,pr.y.y);
}
return {{mnX,mxX},{mnY,mxY}};
}
void give_initial_chart(int h,int w, vector<int> y, vector<int> x)
{
H=h, W=w;
X=x, Y=y;
build();
}
int swap_seats(int a, int b)
{
swap(X[a],X[b]);
swap(Y[a],Y[b]);
update(a), update(b);
int ret=0;
int ptr=0;
int prev[4]={(int)1e9,-1,(int)1e9,-1};
int from=0;
while(ptr<H*W)
{
auto gt=get(from,ptr);
gt.x.x=min(gt.x.x,prev[0]);
gt.y.x=min(gt.y.x,prev[2]);
gt.x.y=max(gt.x.y,prev[1]);
gt.y.y=max(gt.y.y,prev[3]);
int where=(gt.x.y-gt.x.x+1)*(gt.y.y-gt.y.x+1)-1;
from=ptr+1;
if(where==ptr)
{
ret++;
ptr+=min(gt.x.y-gt.x.x+1,gt.y.y-gt.y.x+1);
prev[0]=gt.x.x;
prev[1]=gt.x.y;
prev[2]=gt.y.x;
prev[3]=gt.y.y;
}
else
{
ptr=where;
prev[0]=gt.x.x;
prev[1]=gt.x.y;
prev[2]=gt.y.x;
prev[3]=gt.y.y;
}
}
return ret;
}
