#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct limite {
int haut,bas,gauche,droite;
void afficher(){
cout<<"haut "<<haut<<" bas "<<bas<<" gauche "<<gauche<<" droite "<<droite<<endl;
}
};
const int TAILLEMAXI=1000*1000+2,INFINI=1000*1000*1000;
vector<vector<int>> grille;
vector<int> lig,col;
int nblig,nbcol;
int rep;
bool ok[TAILLEMAXI];
vector<limite> limites;
void change(int deb,int fin){
limite avant=limites[deb-1];
for (int i=deb;i<=fin;i++){
avant.haut=min(avant.haut,lig[i-1]);
avant.bas=max(avant.bas,lig[i-1]);
avant.gauche=min(avant.gauche,col[i-1]);
avant.droite=max(avant.droite,col[i-1]);
//avant.afficher();
limites[i]=avant;
if (ok[i]){
rep--;
ok[i]=false;
}
if ((avant.bas-avant.haut+1)*(avant.droite-avant.gauche+1)==i){
rep++;
//cout<<i<<endl;
ok[i]=true;
}
}
}
void give_initial_chart(int nblignes, int nbcolonnes, vector<int> l, vector<int> c) {
nblig=nblignes;
nbcol=nbcolonnes;
vector<vector<int>> tab(nblig,vector<int>(nbcol,0));
for (int i=0;i<nblig*nbcolonnes;i++){
tab[l[i]][c[i]]=i+1;
}
grille=tab;
lig=l;
col=c;
limites.push_back({INFINI,-1,INFINI,-1});
for (int i=1;i<=nblig*nbcol;i++){
limites.push_back({0,0,0,0});
}
change(1,nblig*nbcol);
//cout<<rep<<endl;
}
int swap_seats(int a, int b) {
a++;
b++;
if (b<a){
swap(a,b);
}
swap(lig[a-1],lig[b-1]);
swap(col[a-1],col[b-1]);
change(a,b);
return rep;
}
