#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> p2;
const int N=1e6+5;
const int K=(1<<21)+5;
const int inf=1e9;
int h,w,n;
vector<int> r(N),c(N);
struct minsegtree{
int t[K];
void build(int l,int r,int i,vector<int> &a){
if(l==r)return void(t[i]=a[l]);
int m=(l+r)/2;
build(l,m,i*2,a);
build(m+1,r,i*2+1,a);
t[i]=min(t[i*2],t[i*2+1]);
}
void build(vector<int> &a){
build(1,n,1,a);
}
void update(int l,int r,int i,int x,int v){
if(x<l||r<x)return;
if(l==r)return void(t[i]=v);
int m=(l+r)/2;
update(l,m,i*2,x,v);
update(m+1,r,i*2+1,x,v);
t[i]=min(t[i*2],t[i*2+1]);
}
void update(int x,int v){
update(1,n,1,x,v);
}
int query(int l,int r,int i,int x,int y){
if(y<l||r<x)return inf;
if(x<=l&&r<=y)return t[i];
int m=(l+r)/2;
return min(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
}
int query(int x,int y){
return query(1,n,1,x,y);
}
}mnr,mnc;
struct maxsegtree{
int t[K];
void build(int l,int r,int i,vector<int> &a){
if(l==r)return void(t[i]=a[l]);
int m=(l+r)/2;
build(l,m,i*2,a);
build(m+1,r,i*2+1,a);
t[i]=max(t[i*2],t[i*2+1]);
}
void build(vector<int> &a){
build(1,n,1,a);
}
void update(int l,int r,int i,int x,int v){
if(x<l||r<x)return;
if(l==r)return void(t[i]=v);
int m=(l+r)/2;
update(l,m,i*2,x,v);
update(m+1,r,i*2+1,x,v);
t[i]=max(t[i*2],t[i*2+1]);
}
void update(int x,int v){
update(1,n,1,x,v);
}
int query(int l,int r,int i,int x,int y){
if(y<l||r<x)return -inf;
if(x<=l&&r<=y)return t[i];
int m=(l+r)/2;
return max(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
}
int query(int x,int y){
return query(1,n,1,x,y);
}
}mxr,mxc;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h=H,w=W;
n=h*w;
for(int i=1;i<=n;i++){
r[i]=R[i-1];
c[i]=C[i-1];
}
mnr.build(r);
mxr.build(r);
mnc.build(c);
mxc.build(c);
}
int swap_seats(int a, int b){
a++,b++;
swap(r[a],r[b]);
swap(c[a],c[b]);
mnr.update(a,r[a]);
mnr.update(b,r[b]);
mnc.update(a,c[a]);
mnc.update(b,c[b]);
mxr.update(a,r[a]);
mxr.update(b,r[b]);
mxc.update(a,c[a]);
mxc.update(b,c[b]);
int idx=1,ans=0;
while(idx<=n){
int sz=(mxr.query(1,idx)-mnr.query(1,idx)+1)*(mxc.query(1,idx)-mnc.query(1,idx)+1);
if(sz==idx){
ans++;
idx++;
}else{
idx=sz;
}
}
return ans;
}
