#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;
}
int cnt=0;
vector<bool> vec;
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]};
}
pair<int,int> m=seats[1],M=seats[1];
vec.resize(N+1,false);
for(int i=1;i<=N;i++){
m.first=min(m.first,seats[i].first);
m.second=min(m.second,seats[i].second);
M.first=max(M.first,seats[i].first);
M.second=max(M.second,seats[i].second);
if((M.first-m.first+1)*(M.second-m.second+1==i)){
vec[i]=true;
cnt++;
}
}
build(1,1,N);
}
int swap_seats(int a, int b) {
a++;b++;
update(1,1,N,a,seats[b]);
update(1,1,N,b,seats[a]);
swap(seats[a],seats[b]);
if(a>b){
swap(a,b);
}
for(int i=a;i<=b;i++){
pair<int,int> m=querym(1,1,N,i),M=queryM(1,1,N,i);
bool tmp=((M.first-m.first+1)*(M.second-m.second+1)==i);
if(tmp&&!vec[i]){
cnt++;
}else if(!tmp&&vec[i]){
cnt--;
}
vec[i]=tmp;
}
return cnt;
}
