#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int> R;
vector<int> C;
int lv1[1100100 * 4];
int rv1[1100100 * 4];
int lv2[1100100 * 4];
int rv2[1100100 * 4];
void hupdate(int i, int s, int e, int in, int k){
if(s == e){
lv1[i] = k;
rv1[i] = k;
return;
}
int m = (s + e)/2;
if(in <= m){
hupdate(i * 2,s,m,in,k);
}
else{
hupdate(i * 2 + 1,m + 1, e, in, k);
}
lv1[i] = min(lv1[i * 2], lv1[i * 2 + 1]);
rv1[i] = max(rv1[i * 2], rv1[i * 2 + 1]);
}
pair<int,int> hquery(int i, int s, int e, int S, int E){
if(S <= s && e <= E){
return {lv1[i],rv1[i]};
}
int m = (s + e)/2;
pair<int,int> ii = {1100100100, -1};
if(S <= m){
pair<int,int> ii1 = hquery(i * 2,s,m,S,E);
ii.first = min(ii.first, ii1.first);
ii.second = max(ii.second, ii1.second);
}
if(m < E){
pair<int,int> ii1 = hquery(i * 2 + 1,m + 1,e,S,E);
ii.first = min(ii.first, ii1.first);
ii.second = max(ii.second, ii1.second);
}
return ii;
}
void cupdate(int i, int s, int e, int in, int k){
if(s == e){
lv2[i] = k;
rv2[i] = k;
return;
}
int m = (s + e)/2;
if(in <= m){
cupdate(i * 2,s,m,in,k);
}
else{
cupdate(i * 2 + 1,m + 1, e, in, k);
}
lv2[i] = min(lv2[i * 2], lv2[i * 2 + 1]);
rv2[i] = max(rv2[i * 2], rv2[i * 2 + 1]);
}
pair<int,int> cquery(int i, int s, int e, int S, int E){
if(S <= s && e <= E){
return {lv2[i],rv2[i]};
}
int m = (s + e)/2;
pair<int,int> ii = {1100100100, -1};
if(S <= m){
pair<int,int> ii1 = cquery(i * 2,s,m,S,E);
ii.first = min(ii.first, ii1.first);
ii.second = max(ii.second, ii1.second);
}
if(m < E){
pair<int,int> ii1 = cquery(i * 2 + 1,m + 1,e,S,E);
ii.first = min(ii.first, ii1.first);
ii.second = max(ii.second, ii1.second);
}
return ii;
}
int H,W;
int HW;
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 < H * W ; i++){
hupdate(1,0,HW-1,i,R[i]);
cupdate(1,0,HW-1,i,C[i]);
}
}
int swap_seats(int a, int b) {
swap(R[a],R[b]);
swap(C[a],C[b]);
hupdate(1,0,HW-1,a,R[a]);
hupdate(1,0,HW-1,b,R[b]);
cupdate(1,0,HW-1,a,C[a]);
cupdate(1,0,HW-1,b,C[b]);
int num = 2;
int v = 2;
int s = 1;
int e = 1;
while(v < H * W){
pair<int,int> ii = hquery(1,0,HW-1,0, v - 1);
pair<int,int> ii1 = cquery(1,0,HW-1,0, v - 1);
s = (ii.second - ii.first + 1);
e = (ii1.second - ii1.first + 1);
if( s * e == v ){
v = min( (s + 1) * e, s * (e + 1) );
num++;
}
v = max(v, s * e);
}
return num;
}
