#include "seats.h"
#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;
///Si ce n'est que sur une ligne.
struct Noeud {
int mini, maxi, nBons, deb, fin;
bool ok;
};
const int N = (1 << 20);
Noeud arbre[N * 2];
int nVals;
void combine(int noeud){
arbre[noeud].deb = arbre[noeud * 2].deb;
arbre[noeud].fin = arbre[noeud * 2 + 1].fin;
arbre[noeud].mini = min(arbre[noeud * 2].mini, arbre[noeud * 2 + 1].mini);
arbre[noeud].maxi = max(arbre[noeud * 2].maxi, arbre[noeud * 2 + 1].maxi);
arbre[noeud].ok = (arbre[noeud].deb == arbre[noeud].mini && arbre[noeud].fin == arbre[noeud].maxi);
arbre[noeud].nBons = arbre[noeud * 2].nBons + (arbre[noeud * 2].ok * arbre[noeud * 2 + 1].nBons);
}
int positions[N];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
for (int noeud = 1; noeud < 2 * N; ++noeud)
arbre[noeud] = {N + 1, - 1, 0, N + 1, N + 1};
nVals = H * W;
for (int iVal = 0; iVal < nVals; ++iVal){
positions[iVal] = C[iVal];
arbre[N + positions[iVal]] = {iVal, iVal, 1, positions[iVal], positions[iVal], 1};
}
for (int noeud = N - 1; noeud > 0; --noeud)
combine(noeud);
}
void update(int iVal){
int noeud = N + iVal;
arbre[noeud] = {iVal, iVal, 1, positions[iVal], positions[iVal], 1};
noeud /= 2;
for (; noeud > 0; noeud /= 2)
combine(noeud);
}
int swap_seats(int a, int b) {
swap(positions[a], positions[b]);
update(a);
update(b);
return arbre[1].nBons;
}
