#include "seats.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
int H,W;
vector<int> X,Y;
vector<pair<pair<int,int>,pair<int,int>>> sgt; //X(min,max) Y(min,max)
void build(int p=1, int l=0, int r=H*W-1)
{
if(l==r)
{
sgt[p]={{X[l],X[l]},{Y[l],Y[l]}};
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
sgt[p].x.x=min(sgt[p*2].x.x, sgt[p*2+1].x.x);
sgt[p].y.x=min(sgt[p*2].y.x, sgt[p*2+1].y.x);
sgt[p].x.y=max(sgt[p*2].x.y, sgt[p*2+1].x.y);
sgt[p].y.y=max(sgt[p*2].y.y, sgt[p*2+1].y.y);
}
void update(int id, int p=1, int l=0, int r=H*W-1)
{
if(l==r)
{
sgt[p]={{X[l],X[l]},{Y[l],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].x.x=min(sgt[p*2].x.x, sgt[p*2+1].x.x);
sgt[p].y.x=min(sgt[p*2].y.x, sgt[p*2+1].y.x);
sgt[p].x.y=max(sgt[p*2].x.y, sgt[p*2+1].x.y);
sgt[p].y.y=max(sgt[p*2].y.y, sgt[p*2+1].y.y);
}
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];
int mid=(l+r)/2; // 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;
sgt.resize(4*H*W);
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;
while(ptr<H*W)
{
auto gt=get(0,ptr);
int where=(gt.x.y-gt.x.x+1)*(gt.y.y-gt.y.x+1)-1;
if(where==ptr)
{
ret++;
ptr++;
}
else ptr=where;
}
return ret;
}
