#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();
}
}
ll 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;
for(int i = 0 ; i < hw ; i ++){
alto = maxH->query(0, i) - minH->query(0, i) + 1;
ancho = maxC->query(0, i) - minC->query(0, i) + 1;
if(ancho * alto == i + 1){
ans ++ ;
i += min(ancho, alto) -1;
//cout << i << endl;
}else{
i = ancho*alto-2;
}
}
//cout << endl;
return ans;
}
