#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;
bool acum[1000002];
int ans;
void updetiar(int dd, int ht);
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);
memset(acum, false, sizeof acum);
ans = 0;
updetiar(0, hw-1);
}
void updetiar(int dd, int ht){
ll alto, ancho;
//cout << " c " << dd << " " << ht << endl;
int minimoH = minH->query(0, dd), minimoC = minC->query(0, dd), maximoH = maxH->query(0, dd), maximoC = maxC->query(0, dd), nextI;
for(int i = dd ; i <= ht ;){
//cout << i << endl;
//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;
bool flag = false;
if(ancho * alto == i + 1){
//ans ++ ;
flag = true;
//nextI = i + min(ancho, alto);
//cout << i << endl;
}else{
//nextI = ancho*alto-1;
}
if(nextI < i+20 and nextI <= ht){
for(int j = i+1 ; j <= nextI ; j ++){
minimoH = min(minimoH, r[j]);
minimoC = min(minimoC, c[j]);
maximoH = max(maximoH, r[j]);
maximoC = max(maximoC, c[j]);
}
}else if(nextI <= ht){
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);
}
if(acum[i] and !flag){
ans -- ;
//cout << "se perdio " << i << endl;
}else if(!acum[i] and flag){
ans ++ ;
}
acum[i] = flag;
i = nextI;
}
}
int swap_seats(int a, int b) {
if(a > b)swap(a, 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]);
updetiar(min(a, b), max(a, b));
//cout << endl;
return ans;
}
