#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define debug(a) cout << #a << " = " << a << endl
struct x{
int MAXf;
int MINf;
int MAXc;
int MINc;
int hizq;
int hder;
};
struct y{
int fil;
int col;
};
int cont,n,p,res;
x uso,maximos;
x ST[2100000];
y id[1000002];
int mif, maf, mic, mac;
void dd(x nodo){
debug(nodo.MAXf);
debug(nodo.MINf);
debug(nodo.MAXc);
debug(nodo.MINc);
debug(nodo.hizq);
debug(nodo.hder);
debug(" ");
}
void d(int p){
x nodo;
debug(p);
nodo = ST[p];
dd(nodo);
}
void h(int pos){
ST[pos].hizq = cont++;
ST[pos].hder = cont++;
}
void crea(int ini, int fin, int num, int r, int c, int pos) {
int mitad;
if (ini == fin && ini == num) {
ST[pos].MAXf = r;
ST[pos].MAXc = c;
ST[pos].MINf = r;
ST[pos].MINc = c;
return;
}
else if (ini <= num && fin >= num) {
mitad = (ini+fin) / 2;
if (ST[pos].hizq == 0) h(pos);
crea(ini, mitad, num, r, c, ST[pos].hizq);
crea(mitad + 1, fin, num, r, c, ST[pos].hder);
ST[pos].MAXf = max(ST[ST[pos].hizq].MAXf, ST[ST[pos].hder].MAXf);
ST[pos].MINf = min(ST[ST[pos].hizq].MINf, ST[ST[pos].hder].MINf);
ST[pos].MAXc = max(ST[ST[pos].hizq].MAXc, ST[ST[pos].hder].MAXc);
ST[pos].MINc = min(ST[ST[pos].hizq].MINc, ST[ST[pos].hder].MINc);
return;
}
return;
}
void query(int nodo, int ini, int fin, int r) {
int mitad;
if (fin <= r) {
mif = min(mif, ST[nodo].MINf);
maf = max(maf, ST[nodo].MAXf);
mic = min(mic, ST[nodo].MINc);
mac = max(mac, ST[nodo].MAXc);
return;
}
else if (ini <= r) {
mitad = (ini+fin) / 2;
query(ST[nodo].hizq,ini,mitad, r);
query(ST[nodo].hder,mitad+1,fin, r);
return;
}
return;
}
bool checa(int val) {
int l1,l2;
l1 = maf - mif + 1;
l2 = mac - mic + 1;
l1 *= l2;
return (l1 == (val+1));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H*W;
cont = 2;
rep(i, 0, n-1) {
id[i] = {R[i], C[i]};
crea(0, n-1, i, R[i], C[i], 1);
}
}
int swap_seats(int a, int b) {
crea(0, n-1, b, id[a].fil, id[a].col, 1);
crea(0, n-1, a, id[b].fil, id[b].col, 1);
swap(id[a], id[b]);
p = 0;
res = 0;
while (p < n) {
mif = INT_MAX;
maf = 0;
mic = INT_MAX;
mac = 0;
query(1, 0, n-1, p);
if (checa(p)) {
res++;
p++;
}
else {
p = max(p + 1, (maf - mif + 1) * (mac - mic + 1) - 1);
}
}
return res;
}
