#include "seats.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
std::vector<int> r, c;
vector<int>aux;
ll h, w, hw;
struct segTree{
int dd, ht, mid;
ll val;
bool isMax;
segTree *L, *R;
segTree(int l, int rr, bool maximos){
dd = l;
ht = rr;
mid = (dd + ht)/2;
val = 0;
isMax = maximos;
if(l != rr){
L = new segTree(l, mid, maximos);
R = new segTree(mid+1, ht, maximos);
if(isMax and L->val > R->val)val = L->val;
else if(isMax)val = R->val;
else if(L->val < R->val)val = L->val;
else val = R->val;
}else{
val = aux[l];
}
}
void update(){
if(isMax and L->val > R->val)val = L->val;
else if(isMax)val = R->val;
else if(L->val < R->val)val = L->val;
else val = R->val;
}
void cambiar(int pos, int cuanto){
if(dd == ht)val = cuanto;
else{
if(pos <= mid)L->cambiar(pos, cuanto);
else R->cambiar(pos, cuanto);
update();
}
}
int query(int l, int rr){
if(dd == l and rr == ht)return val;
if( rr<= mid)return L->query(l, rr);
if(mid < l)return R->query(l, rr);
if(isMax){
return max(L->query(l, mid), R->query(mid+1, rr));
}else return min(L->query(l, mid), R->query(mid+1, rr));
}
};
segTree *maxH, *minH, *maxC, *minC;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r = R;
c = C;
h = H;
w = W;
hw = h*w;
for(int i = 0 ; i < hw ; i ++)aux.pb(R[i]);
maxH = new segTree(0, hw-1, true);
minH = new segTree(0, hw-1, false);
for(int i = 0 ; i < hw ; i ++)aux[i] = C[i];
maxC = new segTree(0, hw-1, true);
minC = new segTree(0, hw-1, false);
}
int swap_seats(int a, int b) {
maxH->cambiar(a, r[b]);
minH->cambiar(a, r[b]);
maxH->cambiar(b, r[a]);
minH->cambiar(b, r[a]);
maxC->cambiar(a, c[b]);
minC->cambiar(a, c[b]);
maxC->cambiar(b, c[a]);
minC->cambiar(b, c[a]);
swap(r[a], r[b]);
swap(c[a], c[b]);
ll alto, ancho, ans = 0;
int minimoH = r[0], minimoC = c[0], maximoH = r[0], maximoC = c[0], nextI;
for(int i = 0 ; i < hw ;){
//alto = maxH->query(0, i) - minH->query(0, i) + 1;
//ancho = maxC->query(0, i) - minC->query(0, i) + 1;
alto = maximoH - minimoH + 1;
ancho = maximoC - minimoC + 1;
nextI = i+1;
if(ancho * alto == i + 1){
ans ++ ;
nextI = i + min(ancho, alto);
//cout << i << endl;
}else{
nextI = ancho*alto-1;
}
if(nextI == i+1 and i+1 < hw){
minimoH = min(minimoH, r[i+1]);
minimoC = min(minimoC, c[i+1]);
maximoH = max(maximoH, r[i+1]);
maximoC = max(maximoC, c[i+1]);
}else if(nextI < hw){
minimoH = min(minH->query(i+1, nextI), minimoH);
maximoH = max(maxH->query(i+1, nextI), maximoH);
minimoC = min(minC->query(i+1, nextI), minimoC);
maximoC = max(maxC->query(i+1, nextI), maximoC);
}
i = nextI;
}
//cout << endl;
return ans;
}
