#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int h,w,N;
vector<pair<int,int>> segm,segM,seats;
void build(int id,int l,int r){
if(l==r){
segm[id]=segM[id]=seats[l];
return;
}
int m=l+(r-l)/2;
build(2*id,l,m);
build(2*id+1,m+1,r);
segm[id].first=min(segm[id*2].first,segm[id*2+1].first);
segm[id].second=min(segm[id*2].second,segm[id*2+1].second);
segM[id].first=max(segM[id*2].first,segM[id*2+1].first);
segM[id].second=max(segM[id*2].second,segM[id*2+1].second);
}
void update(int id,int l,int r,int &x,pair<int,int> &v){
if(l==r){
segm[id]=segM[id]=v;
return;
}
int m=l+(r-l)/2;
if(x<=m){
update(id*2,l,m,x,v);
}else{
update(id*2+1,m+1,r,x,v);
}
segm[id].first=min(segm[id*2].first,segm[id*2+1].first);
segm[id].second=min(segm[id*2].second,segm[id*2+1].second);
segM[id].first=max(segM[id*2].first,segM[id*2+1].first);
segM[id].second=max(segM[id*2].second,segM[id*2+1].second);
}
pair<int,int> querym(int id,int l,int r,int &R){
if(l>R){
return {1e9,1e9};
}else if(r<=R){
return segm[id];
}
int m=l+(r-l)/2;
pair<int,int> ans=querym(id*2,l,m,R),tmp=querym(id*2+1,m+1,r,R);
ans.first=min(ans.first,tmp.first);
ans.second=min(ans.second,tmp.second);
return ans;
}
pair<int,int> queryM(int id,int l,int r,int &R){
if(l>R){
return {-1,-1};
}else if(r<=R){
return segM[id];
}
int m=l+(r-l)/2;
pair<int,int> ans=queryM(id*2,l,m,R),tmp=queryM(id*2+1,m+1,r,R);
ans.first=max(ans.first,tmp.first);
ans.second=max(ans.second,tmp.second);
return ans;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
N=H*W;
segm.resize(4*N);
segM.resize(4*N);
h=H;w=W;
seats.resize(N+1);
for(int i=0;i<N;i++){
seats[i+1]={R[i],C[i]};
}
build(1,1,N);
}
int swap_seats(int a, int b) {
int cnt=1,ans=0;a++;b++;
update(1,1,N,a,seats[b]);
update(1,1,N,b,seats[a]);
swap(seats[a],seats[b]);
int rnd = 0;
while(cnt<=N){
++rnd;
pair<int,int> m=querym(1,1,N,cnt),M=queryM(1,1,N,cnt);
// cout << m.first << ' ' << m.second << ' ' << M.first << ' ' << M.second << '\n';
int nxt;
if((M.first-m.first+1)*(M.second-m.second+1)==cnt){
ans++;
nxt = cnt + min(M.first-m.first+1,M.second-m.second+1);
}else{
nxt = (M.first-m.first+1)*(M.second-m.second+1);
}
assert(nxt > cnt);
cnt = nxt;
}
return ans;
}
