#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)(x.size())
const int MX = (int)(1e6+3);
const int INF = (int)(1e9);
typedef pair<int,int> ii;
int ans[MX],fen[MX],N;
vector<int> X,Y;
ii range[MX][2];
pair<ii,ii> st[4*MX];
void update(int idx,int val){
for (int i = idx; i <= N; i+=(i&(-i)))
fen[i]+=val;
}
int get(int idx){
int h=0;
for (int i = idx; i >= 1; i-=(i&(-i)))
h+=fen[i];
return h;
}
void add(int a,int b,int val){
update(a,val);
if(b!=N)update(b+1,-val);
}
void build(int node,int l,int r){
if(l==r){
st[node]={{X[l],X[l]},{Y[l],Y[l]}};
return;
}
int med=(l+r)>>1;
build(node*2,l,med),build(node*2+1,med+1,r);
st[node].fi={min(st[node*2].fi.fi,st[node*2+1].fi.fi),max(st[node*2].fi.se,st[node*2+1].fi.se)};
st[node].se={min(st[node*2].se.fi,st[node*2+1].se.fi),max(st[node*2].se.se,st[node*2+1].se.se)};
}
void update(int node,int l,int r,int idx){
if(l>idx || r<idx)
return;
if(l==r){
st[node]={{X[l],X[l]},{Y[l],Y[l]}};
return;
}
int med=(l+r)>>1;
update(node*2,l,med,idx),update(node*2+1,med+1,r,idx);
st[node].fi={min(st[node*2].fi.fi,st[node*2+1].fi.fi),max(st[node*2].fi.se,st[node*2+1].fi.se)};
st[node].se={min(st[node*2].se.fi,st[node*2+1].se.fi),max(st[node*2].se.se,st[node*2+1].se.se)};
}
pair<ii,ii> query(int node,int l,int r,int i,int j){
if(l>j || r<i)
return {{INF,-1},{INF,-1}};
if(l>=i && r<=j)return st[node];
int med=(l+r)>>1;
pair<ii,ii> q=query(node*2,l,med,i,j),q2=query(node*2+1,med+1,r,i,j);
return {{min(q.fi.fi,q2.fi.fi),max(q.fi.se,q2.fi.se)},{min(q.se.fi,q2.se.fi),max(q.se.se,q2.se.se)}};
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
X=R,Y=C;
N=sz(X);
build(1,0,N-1);
for (int i = 0; i < H*W; ++i)
{
if(i){
int k=get(i);
add(i+1,i+1,k);
}
pair<ii,ii> q=query(1,0,N-1,0,i);
if(((q.fi.se-q.fi.fi+1)*(q.se.se-q.se.fi+1))==(i+1))add(i+1,i+1,1);
}
}
int swap_seats(int a, int b) {
if(a>b)swap(a,b);
swap(X[a],X[b]),swap(Y[a],Y[b]);
update(1,0,N-1,a),update(1,0,N-1,b);
if(b!=N){
int k=get(b+1);
add(b+2,N,-k);
}
for (int i = a; i <= b; ++i)
{
int k=get(i+1);
add(i+1,i+1,-k);
if(i){
int k=get(i);
add(i+1,i+1,k);
}
pair<ii,ii> q=query(1,0,N-1,0,i);
if(((q.fi.se-q.fi.fi+1)*(q.se.se-q.se.fi+1))==(i+1))add(i+1,i+1,1);
}
if(b!=N){
int k=get(b+1);
add(b+2,N,k);
}
return get(N);
}
