#include "seats.h"
#include <iostream>
using namespace std;
const int N = 1e6+10;
const int inf = 1e9;
struct node
{
int mxi, mni, mxj, mnj;
};
int n;
vector<int> R, C;
node sg[4*N];
void upd(int v, int l, int r, int i)
{
if (l+1==r)
{
sg[v].mxi = sg[v].mni = R[i];
sg[v].mxj = sg[v].mnj = C[i];
return;
}
int md = (l+r)/2;
if (i < md)
upd(v*2+1, l, md, i);
else
upd(v*2+2, md, r, i);
sg[v].mxi = max(sg[v*2+1].mxi, sg[v*2+2].mxi);
sg[v].mni = min(sg[v*2+1].mni, sg[v*2+2].mni);
sg[v].mxj = max(sg[v*2+1].mxj, sg[v*2+2].mxj);
sg[v].mnj = min(sg[v*2+1].mnj, sg[v*2+2].mnj);
}
node qr(int v, int l, int r, int i, int j)
{
if (l>=r || i >= r || j <= l)
return {-inf, inf, -inf, inf};
// cout << " " << l << " " << r << "\n";
if (i <= l && j >= r)
{
// cout << sg[v].mnj << "\n";
return sg[v];
}
int md = (l+r)/2;
node lv = qr(v*2+1, l, md, i, j);
node ds = qr(v*2+2, md, r, i, j);
node tr = {max(lv.mxi, ds.mxi), min(lv.mni, ds.mni), max(lv.mxj, ds.mxj), min(lv.mnj, ds.mnj)};
// cout << l << " " << r << " || " << tr.mxi << " " << tr.mni << " " << tr.mxj << " " << tr.mnj << "\n";
return tr;
}
void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c)
{
R=r;C=c;
n = H*W;
for (int i = 0; i < n; i++)
upd(0, 0, n, i);
}
int swap_seats(int a, int b)
{
if (a>b)
swap(a, b);
swap(R[a], R[b]);
swap(C[a], C[b]);
upd(0, 0, n, a);
upd(0, 0, n, b);
int rez=0, tr=0;
while (tr < n)
{
node zac = qr(0, 0, n, 0, tr+1);
int dx = zac.mxi-zac.mni+1, dy = zac.mxj-zac.mnj+1;
if (dx*dy==tr+1)
{
tr++;
rez++;
}
else
tr=dx*dy-1;
}
return rez;
}
