#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
std::vector<int> x,y;
int H,W;
pair<pair<int,int>,pair<int,int>> aint[4000005];
pair<pair<int,int>,pair<int,int>> combine(pair<pair<int,int>,pair<int,int>> a, pair<pair<int,int>,pair<int,int>> b)
{
return {{min(a.first.first,b.first.first),max(a.first.second,b.first.second)},{min(a.second.first,b.second.first),max(a.second.second,b.second.second)}};
}
pair<pair<int,int>,pair<int,int>> emp = {{INF,-INF},{INF,-INF}};
void upd(int nod, int st, int dr, int poz, pair<int,int> newv)
{
if(st==dr)
{
aint[nod] = {{newv.first,newv.first},{newv.second,newv.second}};
return;
}
int mij=(st+dr)/2;
if(poz<=mij) upd(nod*2,st,mij,poz,newv);
else upd(nod*2+1,mij+1,dr,poz,newv);
aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
pair<pair<int,int>,pair<int,int>> qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return emp;
if(le==st && dr==ri)
return aint[nod];
int mij=(st+dr)/2;
return combine(qry(nod*2,st,mij,le,min(mij,ri)),
qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
pair<pair<int,int>,pair<int,int>> pref;
int cautare_binara(int nod, int st, int dr, pair<pair<int,int>,pair<int,int>> cur)
{
if(st==dr)
{
if(combine(cur,aint[nod])==cur)
return -1;
pref = combine(pref, aint[nod]);
return st;
}
int mij=(st+dr)/2;
if(combine(aint[nod*2],cur) != cur)
return cautare_binara(nod*2,st,mij,cur);
else
{
pref = combine(pref, aint[nod*2]);
return cautare_binara(nod*2+1,mij+1,dr,cur);
}
}
set<int> bune;
void calc(int a, int b)
{
if(a>b)
swap(a,b);
auto it = bune.lower_bound(a);
while(it != bune.end() && (*it) <= b)
it = bune.erase(it);
pair<pair<int,int>,pair<int,int>> prec = qry(1,0,H*W-1,0,a-1);
while(1)
{
pref = emp;
int cur = cautare_binara(1,0,H*W-1,prec);
if(cur==-1 || cur-1 > b)
break;
if((prec.first.second-prec.first.first+1) * (prec.second.second-prec.second.first+1) == cur)
{
prec = pref;
bune.insert(cur-1);
}
else
{
prec = pref;
prec = qry(1,0,H*W-1,0,(prec.first.second-prec.first.first+1) * (prec.second.second-prec.second.first+1) - 1);
}
}
}
void give_initial_chart(int citH, int citW, std::vector<int> citR, std::vector<int> citC)
{
H = citH;
W = citW;
x = citR;
y = citC;
for(int i=0;i<H*W;i++)
upd(1,0,H*W-1,i,{x[i],y[i]});
calc(0,H*W-1);
}
int swap_seats(int a, int b)
{
if(H*W==1)
return 1;
swap(x[a],x[b]);
swap(y[a],y[b]);
upd(1,0,H*W-1,a,{x[a],y[a]});
upd(1,0,H*W-1,b,{x[b],y[b]});
calc(a,b);
return bune.size();
}
