#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;
struct Extremums {
int xMin, xMax, yMin, yMax;
int aire(){
return (yMax - yMin + 1) * (xMax - xMin + 1);
}
};
struct Point {
int x, y;
};
int nLigs, nCols, nVals;
const int MAX_VALS = (1 << 20);
const int N = MAX_VALS;
Extremums vals[2 * MAX_VALS];
bool estOk[MAX_VALS];
Point points[MAX_VALS];
int sum = 0;
void combine(int noeud){
vals[noeud].xMin = min(vals[noeud * 2].xMin, vals[noeud * 2 + 1].xMin);
vals[noeud].xMax = max(vals[noeud * 2].xMax, vals[noeud * 2 + 1].xMax);
vals[noeud].yMin = min(vals[noeud * 2].yMin, vals[noeud * 2 + 1].yMin);
vals[noeud].yMax = max(vals[noeud * 2].yMax, vals[noeud * 2 + 1].yMax);
}
Extremums combine(Extremums a, Extremums b){
return {min(a.xMin, b.xMin), max(a.xMax, b.xMax), min(a.yMin, b.yMin), max(a.yMax, b.yMax)};
}
void update(int noeud){
noeud /= 2;
for (; noeud > 0; noeud /= 2)
combine(noeud);
}
Extremums get(int gauche, int droite){
if (droite < gauche) return {N, -1, N, -1};
if (gauche%2 == 1) return combine(vals[gauche], get(gauche + 1, droite));
if (droite%2 == 0) return combine(vals[droite], get(gauche, droite - 1));
return get(gauche/2, droite/2);
}
void construire(int iVal){
if (iVal == 0){
vals[N] = {points[0].x, points[0].x, points[0].y, points[0].y};
update(N + iVal);
return;
}
vals[iVal + N] = vals[N + iVal - 1];
chmin(vals[N + iVal].xMin, points[iVal].x);
chmax(vals[N + iVal].xMax, points[iVal].x);
chmin(vals[iVal + N].yMin, points[iVal].y);
chmax(vals[iVal + N].yMax, points[iVal].y);
sum -= estOk[iVal];
if (vals[iVal + N].aire() == iVal + 1)
estOk[iVal] = true;
else
estOk[iVal] = false;
sum += estOk[iVal];
update(N + iVal);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
for (int noeud = 0; noeud < 2 * N; ++noeud)
vals[noeud] = {N, -1, N, -1};
nLigs = H;
nCols = W;
nVals = nLigs * nCols;
for (int iVal = 0; iVal < nVals; ++iVal)
points[iVal] = {R[iVal], C[iVal]};
vals[0] = {points[0].x, points[0].x, points[0].y, points[0].y};
estOk[0] = true; sum++;
update(N);
for (int iVal = 1; iVal < nVals; ++iVal)
construire(iVal);
}
int getOpt(){
sum = 0;
int pointeur = 1;
while (pointeur != nVals){
Extremums nxt;
while ((nxt = get(N, N + pointeur)).aire() != pointeur)
pointeur = nxt.aire();
sum++;
pointeur++;
}
return sum;
}
int swap_seats(int a, int b) {
swap(points[a], points[b]);
if (abs(a - b) > 10 * 100)
return getOpt();
for (int iVal = min(a, b); iVal <= max(a, b); ++iVal)
construire(iVal);
return sum;
}
