#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;
int 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;
vector<int>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);
for(int i = 0 ; i <= hw ; i ++)acum[i] = false;
int mxH, mxC, mnH, mnC;
for(int i = 0 ; i < hw ; i ++){
mxH = max(R[i], mxH);
mxC = max(C[i], mxC);
mnH = min(R[i], mnH);
mnC = min(C[i], mnC);
maxH.pb(mxH);
maxC.pb(mxC);
minH.pb(mnH);
minC.pb(mnC);
}
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;
int minimoH ,minimoC , maximoH, maximoC, nextI;
if(dd != 0){
minimoH = minH[dd-1], minimoC = minC[dd-1], maximoH = maxH[dd-1], maximoC = maxC[dd-1];
nextI = dd;
minimoH = min(minimoH, r[nextI]);
minimoC = min(minimoC, c[nextI]);
maximoH = max(maximoH, r[nextI]);
maximoC = max(maximoC, c[nextI]);
minH[nextI] = minimoH;
maxH[nextI] = maximoH;
minC[nextI] = minimoC;
maxC[nextI] = maximoC;
}else{
minimoH = r[0];
minimoC = c[0];
maximoH = r[0];
maximoC = c[0];
minH[0] = minimoH;
maxH[0] = maximoH;
minC[0] = minimoC;
maxC[0] = maximoC;
}
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 <= ht){
minimoH = min(minimoH, r[nextI]);
minimoC = min(minimoC, c[nextI]);
maximoH = max(maximoH, r[nextI]);
maximoC = max(maximoC, c[nextI]);
minH[nextI] = minimoH;
maxH[nextI] = maximoH;
minC[nextI] = minimoC;
maxC[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(a, b);
//cout << endl;
return ans;
}
