#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
vector< pair<int, int> > Sillas;
int n;
bool Cuatro = 0;
struct Respuesta{
pair<int, int> Arribita, Abajito;
};
vector<Respuesta> Anteriores;
vector<int> _rbol, Respuestas, Propagar;
void Crear(int i, int d, int p){
if(i == d){
_rbol[p] = Respuestas[i];
return;
}
int P = (i + d) / 2;
Crear(i, P, p * 2);
Crear(P + 1, d, p * 2 + 1);
//_rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
}
void Propagante(int i, int d, int p){
_rbol[p] += Propagar[p] * (d - i + 1);
if(i == d) Respuestas[i] += Propagar[p];
if(p * 2 < _rbol.size() and i != d) Propagar[p * 2] += Propagar[p];
if(p * 2 + 1 < _rbol.size() and i != d) Propagar[p * 2 + 1] += Propagar[p];
Propagar[p] = -0;
}
int Consulta(int i, int d, int p, int I, int D){
Propagante(i, d, p);
if(i >= I and d <= D) return _rbol[p];
if(i > D or d < I) return -0;
int P = (i + d) / 2;
return Consulta(i, P, p * 2, I, D) + Consulta(P + 1, d, p * 2 + 1, I, D);
}
void Actualizar(int i, int d, int p, int I, int D, int v){
Propagante(i, d, p);
if(i >= I and d <= D){
Propagar[p] += v;
Propagante(i, d, p);
return;
}
if(i > D or d < I) return;
int P = (i + d) / 2;
Actualizar(i, P, p * 2, I, D, v);
Actualizar(P + 1, d, p * 2 + 1, I, D, v);
//_rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
n = h * w;
if(n > 1e4) Cuatro = 1;
Sillas.assign(n, {});
for(int i = 0; i < n; i++){
Sillas[i] = {r[i], c[i]};
}
//Cuatro = 1;
if(Cuatro){
pair<int, int> Arriba, Abajo;
int r1 = 0;
for(int i = 0; i < n; i++){
//cerr<<i<<" "<<n<<"\n";
if(i == 0){
r1++;
Arriba.first = Sillas[i].first;
Arriba.second = Sillas[i].second;
Abajo.first = Sillas[i].first;
Abajo.second = Sillas[i].second;
Respuestas.push_back(r1);
continue;
}
if(Sillas[i].first < Arriba.first) Arriba.first = Sillas[i].first;
if(Sillas[i].first > Abajo.first) Abajo.first = Sillas[i].first;
if(Sillas[i].second < Arriba.second) Arriba.second = Sillas[i].second;
if(Sillas[i].second > Abajo.second) Abajo.second = Sillas[i].second;
if(i + 1 == (Abajo.first - Arriba.first + 1) * (Abajo.second - Arriba.second + 1)) r1++;
Respuesta Anterior;
Anterior.Abajito = Abajo;
Anterior.Arribita = Arriba;
Anteriores.push_back(Anterior);
//cerr<<r1<<" ";
Respuestas.push_back(r1);
}
_rbol.assign(n * 4 + 22, 0);
Propagar.assign(n * 4 + 22, 0);
Crear(0, n - 1, 1);
/*cerr<<"\n";
for(int i = 0; i < n; i++) cerr<<Respuestas[i]<<" ";
cerr<<"\n";
for(int i = 0; i < n; i++) cerr<<Consulta(0, n - 1, 1, i, i)<<" ";
cerr<<"\n";*/
}
}
int swap_seats(int a, int b){
if(Cuatro){
swap(Sillas[a], Sillas[b]);
if(a > b) swap(a, b);
int Respuesta_actual = 0;
a--;
pair<int, int> Arriba, Abajo;
if(a > -1){
Respuesta_actual = Consulta(0, n - 1, 1, a, a);
Arriba = Anteriores[a].Arribita;
Abajo = Anteriores[a].Abajito;
}
for(int i = a + 1; i < b; i++){
if(i == 0){
Respuesta_actual++;
Arriba.first = Sillas[i].first;
Arriba.second = Sillas[i].second;
Abajo.first = Sillas[i].first;
Abajo.second = Sillas[i].second;
Anteriores[i].Arribita = Arriba;
Anteriores[i].Abajito = Abajo;
if(i == b - 1) Actualizar(0, n - 1, 1, i, n - 1, Respuesta_actual - Consulta(0, n - 1, 1, i, i));
else Actualizar(0, n - 1, 1, i, i, Respuesta_actual - Consulta(0, n - 1, 1, i, i));
continue;
}
if(Sillas[i].first < Arriba.first) Arriba.first = Sillas[i].first;
if(Sillas[i].first > Abajo.first) Abajo.first = Sillas[i].first;
if(Sillas[i].second < Arriba.second) Arriba.second = Sillas[i].second;
if(Sillas[i].second > Abajo.second) Abajo.second = Sillas[i].second;
Anteriores[i].Arribita = Arriba;
Anteriores[i].Abajito = Abajo;
if(i + 1 == (Abajo.first - Arriba.first + 1) * (Abajo.second - Arriba.second + 1)) Respuesta_actual++;
if(i == b - 1) Actualizar(0, n - 1, 1, i, n - 1, Respuesta_actual - Consulta(0, n - 1, 1, i, i));
else Actualizar(0, n - 1, 1, i, i, Respuesta_actual - Consulta(0, n - 1, 1, i, i));
}
return Consulta(0, n - 1, 1, n - 1, n - 1);
}
swap(Sillas[a], Sillas[b]);
pair<int, int> Arriba, Abajo;
int r = 0;
for(int i = 0; i < n; i++){
if(i == 0){
r++;
Arriba.first = Sillas[i].first;
Arriba.second = Sillas[i].second;
Abajo.first = Sillas[i].first;
Abajo.second = Sillas[i].second;
continue;
}
if(Sillas[i].first < Arriba.first) Arriba.first = Sillas[i].first;
if(Sillas[i].first > Abajo.first) Abajo.first = Sillas[i].first;
if(Sillas[i].second < Arriba.second) Arriba.second = Sillas[i].second;
if(Sillas[i].second > Abajo.second) Abajo.second = Sillas[i].second;
if(i + 1 == (Abajo.first - Arriba.first + 1) * (Abajo.second - Arriba.second + 1)) r++;
}
return r;
}
