#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];
void h(int pos){
ST[pos].hizq = cont++;
ST[pos].hder = cont++;
}
x crea(int ini, int fin, int num ,x des, int pos) {
x a,b;
int mitad;
if (ini == fin && ini == num) {
ST[pos].MAXf = des.MAXf;
ST[pos].MAXc = des.MAXc;
ST[pos].MINf = des.MINf;
ST[pos].MINc = des.MINc;
return ST[pos];
}
else if (ini <= num && fin >= num) {
mitad = (ini+fin) / 2;
if (ST[pos].hizq = 0) h(pos);
a = crea(ini,mitad, num, des,ST[pos].hizq);
b = crea(mitad+1,fin, num, des,ST[pos].hder);
ST[pos].MAXf = max(a.MAXf, b.MAXf);
ST[pos].MINf = max(a.MINf, b.MINf);
ST[pos].MAXc = max(a.MAXc, b.MAXc);
ST[pos].MINc = max(a.MINc, b.MINc);
return ST[pos];
}
return {0, 1000002,0, 1000002,0,0};
}
x query(int nodo, int ini, int fin, int r) {
int mitad;
x a,b;
if (fin <= r) {
return ST[nodo];
}
else if (ini <= r) {
mitad = (ini+fin) / 2;
a = query(ST[nodo].hizq,ini,mitad, r);
b = query(ST[nodo].hder,mitad+1,fin, r);
a.MAXf = max(a.MAXf, b.MAXf);
a.MINf = min(a.MINf, b.MINf);
a.MAXc = max(a.MAXc, b.MAXc);
a.MINc = min(a.MINc, b.MINc);
return a;
}
return {0, 1000002,0, 1000002,0,0};
}
bool checa(x act, int val) {
int l1,l2;
l1 = act.MAXf - act.MINf + 1;
l2 = act.MAXc - act.MINc + 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,(H*W)-1) {
id[i] = {R[i], C[i]};
uso = {R[i],R[i],C[i],C[i],0,0};
uso = crea(0,(H*W)-1, i, uso,1);
}
}
int swap_seats(int a, int b) {
uso = {id[a].fil, id[a].fil, id[a].col, id[a].col,0,0};
crea(0,n-1,a,uso,1);
uso = {id[b].fil, id[b].fil, id[b].col, id[b].col,0,0};
crea(0,n-1,b,uso,1);
swap(id[a], id[b]);
p = 0;
maximos = {id[p].fil,id[p].fil,id[p].col,id[p].col,0 ,0};
res = 0;
while (p < n) {
maximos = query(1,0,n-1,p);
if (checa(maximos, p)) {
res++;
p++;
}
else p = (maximos.MAXf - maximos.MINf +1)*(maximos.MAXc - maximos.MINc +1);
}
return res;
}
